Skip to content

Remove Nth Node From End of List⚓︎

Link

Description⚓︎

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

Example 1:

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

Example 2:

  • Input: head = [1], n = 1
  • Output: []

Example 3:

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

Constraints:

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

Solution⚓︎

Way 1⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 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) {
        auto dummyHead = new ListNode(0);
        dummyHead->next = head;

        int len = 0;
        for (auto p = dummyHead; p; p = p->next) len++;

        auto p = dummyHead;
        for (int i = 0; i < len - n - 1; i++) p = p->next;
        p->next = p->next->next;

        return dummyHead->next;
    }
};

Way 2⚓︎

To delete the n-th node from back to front, we need to get a reference to the n+1-th node from back to front.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 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) {
        ListNode *dummyHead = new ListNode(-1);
        dummyHead->next = head;
        ListNode *slow = dummyHead;
        ListNode *fast = dummyHead;

        while (n-- && fast) {
            fast = fast->next;
        }
        fast = fast->next;
        while (fast) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;

        return dummyHead->next;
    }
};
  • Time complexity: \(O(n)\);
  • Space complexity: \(O(1)\).

Another way of writing (without memory leak):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 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) {
        auto dummy = new ListNode(0);
        dummy->next = head;

        auto fast = dummy, slow = dummy;
        for (int i = 1; i <= n + 1; i++)
            fast = fast->next;

        while (fast) {
            fast = fast->next;
            slow = slow->next;
        }

        auto temp = slow->next;
        slow->next = slow->next->next;
        delete temp;

        auto res = dummy->next;
        delete dummy;
        return res;
    }
};

We can use two pointers. The first pointer advances the list by \(n+1\) steps from the beginning, while the second pointer starts from the beginning of the list. Now, both pointers are exactly separated by \(n\) nodes apart. We maintain this constant gap by advancing both pointers together until the first pointer arrives past the last node. The second pointer will be pointing at the \(n\)-th node counting from the last. We relink the next pointer of the node referenced by the second pointer to point to the node's next next node.