How to Remove Nth Node From End of List in C/C++?

Remove the nth node from the end of a singly linked list and return its head. For example, input: 1-2-3-4-5, and n = 2. Removing the second node from the end, the linked list becomes 1-2-3-5. You can assume the n will always be valid (less than the length of the linked list).

Two passes

The straightforward two-passes will be first to detect the length of the linked list and the second pass is to delete its n-th node. As the length of the linked list is no known without a pass, it would be difficult to know which node from the end to delete in the first place.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int r = 0;
        auto p = head;
        // first pass - get the length        
        while (head != NULL) {
            r ++;
            head = head->next;
        }
        // removing the head
        if (r == n) {
            p = p->next;
            return p;
        }
        head = p;
        // second pass, locate the node
        for (int i = 0; i < r - n - 1; i ++) {
            head = head->next;
        }
        // and delete it
        head->next = head->next->next;
        return p; // stored head
    }
};

One pass

The trick of using One-pass is to have two pointers, fast and slow one. The slow pointer will only advance itself after n-th round, so when the fast pointer reaches the end, the slow pointer will be exactly n-th node from the end.

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        auto front = head, back = head;
        while (front) {
            front = front->next;
            if (n-- < 0) {
                back = back->next;
            }
        }
        if (n == 0) {
            head = head->next;
        } else {
            back->next = back->next->next;
        }
        return head;
    }
};

The second method is obviously faster. Both methods need to make deleting-the-head a special case.

–EOF (The Ultimate Computing & Technology Blog) —