Given the head of a linked list, remove the n<sup>th</sup> 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

Thinking process

1 ⇒ 2 ⇒ 3 ⇒ 4 ⇒ 5 ⇒ 6
            ^

Let's consider an example where n = 3, indicating that we want to remove the fourth node. In this case, we need to redirect the pointer from the third node to the fifth node.

The challenge here lies in removing the nth node from the end of the list, excluding the head of the list.

To tackle this, our first task is to locate the target node. If we traverse the list from the head, we won't be able to directly identify this node. Here's where a two-pointer approach comes in handy, reminiscent of the fast-slow pointer method.

Initially, let's have two pointers:

1 ⇒ 2 ⇒ 3 ⇒ 4 ⇒ 5 ⇒ 6
^
slow
^
fast

Moving forward, instruct the fast pointer to advance n steps first:

1 ⇒ 2 ⇒ 3 ⇒ 4 ⇒ 5 ⇒ 6
^
slow
         ^
         fast

When the fast pointer reaches the nth node, prompt the slow pointer to move simultaneously. By the time the fast pointer reaches the end of the list (indicating that fast.next is null), the slow pointer will be positioned at the nth node.

1 ⇒ 2 ⇒ 3 ⇒ 4 ⇒ 5 ⇒ 6
            ^
            slow    
                     ^
                     fast

Now, to remove the nth node from the end of the list, we need to redirect the (n − 1)th node's pointer to the (n−1)th node.

For this, we require the pointer of the (n − 1)thnode. Consequently, we adjust our initial step by instructing the fast pointer to advance(n + 1)th steps instead of n. Subsequently, when the fast pointer reaches the end of the list, the slow pointer will be at the (n − 1)th node.

Just as we traverse a linked list conventionally, we can optimize this process by introducing a dummy head, eliminating the need for an extra check on the head node.

DummyHead ⇒ 1 ⇒ 2 ⇒ 3 ⇒ 4 ⇒ 5 ⇒ 6
^
slow
^
fast

Fast pointer move n steps:

DummyHead ⇒ 1 ⇒ 2 ⇒ 3 ⇒ 4 ⇒ 5 ⇒ 6
^
slow
                    ^
                    fast

Slow pointer move together with fast pointer until fast point reach to the end of the list: slow pointer is now pointin to the (n - 1) th node

DummyHead ⇒ 1 ⇒ 2 ⇒ 3 ⇒ 4 ⇒ 5 ⇒ 6
                    ^
                    slow        
                                ^
                                fast

Solution

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
        let dummyHead = new ListNode(0, head);
        let fast = dummyHead;
        let slow = dummyHead;
        while (n--) {
            fast = fast.next
        }
        while (fast.next) {
            slow = slow.next 
            fast = fast.next
        }
        slow.next = slow.next.next
        return dummyHead.next
    };

Time & Space Complexity Analysis

Time Complexity Analysis:

Let N denote the number of nodes in the linked list. The algorithm traverses the list twice: once to locate the target node and once to adjust pointers for removal. Both traversals have a linear time complexity of O(N).

Space Complexity Analysis: The algorithm utilizes a constant amount of extra space, irrespective of the size of the input list. Hence, the space complexity remains constant, denoted as O(1).

Conclusion:

In summary, we've devised an efficient algorithm to remove the nth node from the end of a linked list, excluding the head node. By utilising a two-pointer approach, we've successfully located the target node and adjusted pointers accordingly to remove it. Furthermore, employing a dummy head has streamlined the process, enhancing its readability and efficiency.