LeetCode Remove Nth Node From End of List: Two Pointers in One Pass

Overview

LeetCode Remove Nth Node From End of List: keep 2 pointers p1 p2 with their distance to be n, p1 points to the desired node once p2 points to the end of list.

LeetCode Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For 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.
Try to do this in one pass.

Solution Analysis: Two Pointers in One Pass

Keep three pointers, `previous`, `deleted`, `the_end`, at first, all of them point to the head of the list, and advance the_end pointer by n positions, and then and advance both `deleted` and `the_end` pointers by one position, then keep moving all of the three pointers one by one position until `the_end` pointer reaches the end of the list, now only by one pass, `deleted` points to exactly the node  when want to delete, and `previous` points to the node just before it. One can easily do deletion by using `previous` and `deleted`. The following code is accepted by the LeetCode OJ to pass this Remove Nth Node From End of List problem:

class Solution {
    public:
        ListNode *removeNthFromEnd(ListNode *head, int n) {
            if (NULL == head || n < 1)
                return head;

            ListNode s(0);
            s.next = head;
            ListNode *p0 = &s;
            ListNode *p1 = head;
            ListNode *p2 = head;

            for (int i = n - 1; i > 0 && p2; --i)
                p2 = p2->next;

            while (p2->next) {
                p0 = p0->next;
                p1 = p1->next;
                p2 = p2->next;
            }

            p0->next = p1->next;
            p1->next = NULL;
            delete p1;
            return s.next;
        }

};

Summary

LeetCode Remove Nth Node From End of List: keep 2 pointers p1 p2 with their distance to be n, p1 points to the desired node once p2 points to the end of list.

Written on April 21, 2013