05 August 2008
Given a linked list, remove the n-th node from the end of list and return its head.
Example:
1
2
3
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.
Follow up:
Could you do this in one pass?
要求移除链表倒数的第N个节点，n不会大于链表的元素总数，如果两次遍历就简单了，先找到链表长度，然后移除len-N+1的的元素，但是要求一次遍历解决问题，所以就要求遍历到这个结点就应该删除了。应用双指针，一个dummy头防止第一个被删了，双指针slow和fast；首先fast指针向前走N步，然后slow和fast同时走，直到fast走到最后一个元素，此时slow指向的就是要移除元素的前一个元素，将下一个元素移除即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1);
ListNode slow = dummy, fast = dummy;
dummy.next = head;
int steps = n;
while (steps > 0) { // fast先走n步
fast = fast.next;
steps--;
}
while (fast.next != null) { // 同时走直到fast走到最后一个，注意这时候slow停在待删除的前一个
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next; //此时slow在待移除节点的前一个，移除
return dummy.next;
}
}