19. Remove Nth Node From End of List (Medium)
https://leetcode.com/problems/remove-nth-node-from-end-of-list/
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?
Solutions
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode ptr1 = head;
int count = 0;
while (count < n) {
ptr1 = ptr1.next;
// if n >= the length of given list, return the node next to head
if (ptr1 == null) {
return head.next;
}
count++;
}
// To reach here, the reversed nth node can't be the head node
// Move one more step, now ptr1 is at node n + 1.
ptr1 = ptr1.next;
ListNode ptr2 = head;
// ptr1 moves x-n-1 steps to reach the end. At the same time, ptr2 move x-n-1
// steps from the head, the index becomes x-(x-n-1)=n+1 counting from the tail. It's
// easy to get the nth node in reverse order which is the next value of node
// n+1(reversed index).
while (ptr1 != null) {
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
ptr2.next = ptr2.next.next;
return head;
}
}