19. Remove Nth Node From End of List
one pass 解法用快慢指针。这里要使用 dummy node,否则无法 deal 像是 ([1], 1) 的 edge case。
Java:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// dummy -> 1 -> null
// slow (0)
// fast(1)
// dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
// slow(0)
// fast(2)
// slow(0)
// fast(2)
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode slow = dummy;
ListNode fast = dummy;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
while (fast != null && fast.next != null) { // we should also have fast != null
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}