LeetCode Remove Nth Node From End of List

Problem statement

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

Example 1:

Container

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

Explanation

Single pointer

One of the approaches to solve this problem is use single pointer by following the below steps

Calculating the length of the linked list
Subtract n from the length
Start from the head and iterate to above (length-n)th node.

A C++ snippet for the above solution is as below:

ListNode* first = head;

while (first != null) {
    length++;
    first = first.next;
}

length -= n;
first = dummy;

while (length > 0) {
    length--;
    first = first.next;
}

first.next = first.next.next;

// dummy next is pointing to the head of the list.
return dummy.next;

The above solution is fine, but the main concern here is the repeated iteration on the linked list.

Consider a case where the list is very huge of length 1,000,000 and we need to remove the 5th node from last. With the above approach, we are iterating over the list twice.

Two pointer

We can use two pointers and remove the node from the list in a single pass. Let's check the algorithm for this.

Algorithm

- Initialize two pointers slow and fast pointing to the head of the list.

- Loop while n > 0
  - fast = fast->next
  - decrement n--

// if fast is nil it means the first node is supposed to be removed
- if fast == nil
  - head = head->next
  - return head

- Loop while fast->next != nil
  - slow = slow->next
  - fast = fast->next

- if slow->next != nil && slow->next->next
  - slow->next = slow->next->next
- else
  - slow->next = nil
- end

return head

C++ solution

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* fast;
        ListNode* slow;

        fast = head;
        slow = head;

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

        if(fast == NULL){
            head = head->next;
            return head;
        }

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

        if(slow->next && slow->next->next){
            slow->next = slow->next->next;
        } else {
            slow->next = NULL;
        }

        return head;
    }
};

Golang solution

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    node := &ListNode{}
	node.Next = head

	slow, fast := node, node

	for ; n > 0; n-- {
		fast = fast.Next
	}

	for ; fast.Next != nil; slow, fast = slow.Next, fast.Next {}

	slow.Next = slow.Next.Next

	return node.Next
}

Javascript solution

var removeNthFromEnd = function(head, n) {
    let fast = head;
    let slow = head;

    while(n > 0) {
        fast = fast.next;
        n--;
    }

    if(fast === null) return head.next;

    while(fast.next !== null) {
        slow = slow.next;
        fast = fast.next;
    }

    slow.next = slow.next.next;

    return head;
};

Dry Run

Let's dry-run our algorithm.

head = [1, 2, 3, 4, 5]
n = 2

Step 1: fast = head, slow = head

        slow, fast -- [1, 2, 3, 4, 5]

Step 2: Loop while n > 0
        2 > 0 = true

        fast = fast->next

                   fast
                    |
        slow -- [1, 2, 3, 4, 5]

        n--
        n = 1

Step 3: Loop while n > 0
        1 > 0 = true

        fast = fast->next

                      fast
                       |
        slow -- [1, 2, 3, 4, 5]

        n--
        n = 0

Step 4: Loop while n > 0
        0 > 0 = false

Step 5: if fast == nil
        = false

Step 6: Loop while fast.next != nil
        = true
        // fast.next pointing to node 4 address

        slow = slow.next
        fast = fast.next

           slow  fast
            |     |
        [1, 2, 3, 4, 5]

Step 7: Loop while fast.next != nil
        = true
        // fast.next pointing to node 5 address

        slow = slow.next
        fast = fast.next

             slow  fast
               |     |
        [1, 2, 3, 4, 5]

Step 8: while fast.next != nil
        = false

Step 9: if slow.next && slow.next.next
        slow is node 3
        slow.next is node 4
        slow.next is node 5

        slow.next = slow.next.next
        // so node 3 next is now pointing to 5

Step 10: return head

         [1, 2, 3, 5]

Container