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;
    }
}

Incorrect Solutions

References