Remove Nth Node From End of List

Problem

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

Examples

Example 1:

Input: head = [1,2,3,4], n = 2

Output: [1,2,4]

Example 2:

Input: head = [5], n = 1

Output: []

Example 3:

Input: head = [1,2], n = 2

Output: [2]

Constraints

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

You should aim for a solution with O(N) time and O(1) space, where N is the length of the given list.

Solution

To find the nth node from the end, we can use two pointers. Start the first pointer n steps forward. Start a new pointer at the head, and walk both in sync. Once the first pointer reaches the end, the new pointer will be n steps away, hence the nth last node. While walking, we need to also have a prev pointer so we can unlink the linked list.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // Walk end n steps forward
        ListNode* end = head;
        for (int i = 0; i < n; ++i) {
            end = end->next;
        }
        // Now walk until end is nullptr
        // This will result in current being N steps from end
        ListNode *current = head;
        ListNode *prev = current;
        while (end) {
            end = end->next;
            prev = current;
            current = current->next;            
        }
 
        // Remove current by pointing prev over to currents next
        // This is a noop if we are removing the head
        prev->next = current->next;
        // Special case for removing the head, we manually point ot next
        if (current == prev) {
            head = head->next;
        }
        return head;
    }
};