Given a linked list, remove the nth node from the end of list and return its head.
For example,
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null)
return null;
if (head.next == null)
return null;
ListNode p1, p2;
int flag = 1;
p1 = p2 = head;
for (int i = 0; i < n; i++) {
if (p2.next != null)
p2 = p2.next;
else
flag = 0;
}
if (flag == 0) {
head = head.next;
} else {
while (p2.next != null) {
p1 = p1.next;
p2 = p2.next;
}
p1.next = p1.next.next;
}
return head;
}
}我提交通过了，这里精髓就是利用双指针一次遍历就能做到，flag必不可少，因为删除的时候必须知道要删除的地方的上一个节点，这样一来，如果是删除头结点，那么会造成p2空指针异常，所以我们得设置一个flag标记一下。
提交成功之后又可以看别人优秀代码。
Approach #1 (Two pass algorithm)
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
int length = 0;
ListNode first = head;
while (first != null) {
length++;
first = first.next;
}
length -= n;
first = dummy;
while (length > 0) {
length--;
first = first.next;
}
first.next = first.next.next;
return dummy.next;
}这就是典型的遍历了两次链表才得到数据。
Approach #2 (One pass algorithm)
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
ListNode second = dummy;
// Advances first pointer so that the gap between first and second is n nodes apart
for (int i = 1; i <= n + 1; i++) {
first = first.next;
}
// Move first to the end, maintaining the gap
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}思想跟我的是一样的，但是经过仔细推敲，他的这种处理头结点的办法比我那个可取，值得学习。
