19. Remove Nth Node From End of List
Tags: ‘Linked List’, ‘Two Pointers’
Given a linked list, remove the n-th node from the end of list and return its head.
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.
Follow up:
Could you do this in one pass?
Solution 1
This is not one pass. Find length first, and increment until pointer before node-to-delete. 注意corner case.
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null) return null;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode curr = dummy;
int length = findLength(head);
int i = length - n;
while (i > 0) {
i--;
curr = curr.next;
}
// curr should be in front of the node to delete
curr.next = curr.next.next;
return dummy.next;
}
private int findLength(ListNode node) {
if (node == null) return 0;
int i = 0;
while (node != null) {
i++;
node = node.next;
}
return i;
}
Solution 2
This looks like ONE PASS, but actually NOT. Should be the same as Solution 1.
Two pointers, increment fast n + 1 steps, then procede until fast hit null
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null) return null;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode slow = dummy, fast = dummy;
for (int i = n; i >= 0; i--) {
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}