0019. Remove Nth Node From End of List

Given the head of a linked list, remove the nth 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

Follow up: Could you do this in one pass?

Analysis

This question can be solved using two pointers method. In order to reach the last nth position, we need to keep a subset of the LinkedList with the length of n and use it to offset the target position. Then we need to handle a special case when n = 1 and we need to remove the first element of the LinkedList.

• Time: $O(n)$
• Space: $O(1)$ if ignore the dummy pointer.

Code

/**
 * 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 *a = new ListNode(-1, head), *b = head;
        while (n--) {
            b = b -> next;
        }
        // when b reaches to the end, a will be n nodes away in front of b
          while (b) {
            a = a -> next;
            b = b -> next;
        }
          // what if we have only one node and we want to remove that one?
        if (a -> next == head) 
            return head -> next;
        if (a -> next)
            a -> next = a -> next -> next;
        return head;
    }
};

---

Last update: April 1, 2022