## Remove Nth Node From End of List Difficulty: Medium

#### Understanding the problem

Problem Description: You are given a linked list, write a program to remove the nth node from the end of the list and return the head.

Problem Note:

• It is guaranteed that n ≤ length of linked list
• Try to do this in one iteration.

Example 1

``````Input: 2->6->1->9, n=2
Output: 2->6->9``````

Example 2

``````Input: 1->2->3->4, n=4
Output: 2->3->4``````

Example 3

``````Input: 4->9->1->2, n=1
Output: 4->9->1``````

The node structure given to you will be→

``````class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x }
}``````

#### Solutions

We will be discussing three different solutions

1. Using Auxillary Space — By saving each node in an array
2. Making two passes through the list — remove the `length- nth` from the beginning.
3. Making one pass through the list — Using fast and slow pointers.

#### 1. Using Auxillary Space

If we could save all the nodes in the array then, we could just remove the pointer of the (length-n-1)th node next to its next.next. In this way the nth node would be removed.

Pseudo Code
``````ListNode removeNthFromEnd(ListNode head, int n) {
ListNode list[]
while(curr!=null){
list.append(curr)
curr = curr.next
}
int size = size(list)
if(size > 1){
if(size > n){
ListNode prev = list[size-n-1]
ListNode  next = null
if(n > 1){
next = list[size-n+1]
}
prev.next = next;
} else {
}
}
return null
}``````
Complexity Analysis

Time Complexity — O(n)

Space Complexity — O(n)

Critical Ideas to Thnik
• Why we are storing each node in an array?
• What will we return if the given value of n is 1?
• Why did we set the list[size-n-1]th node next pointer with list[size-n+1] ?

#### 2. Making two passes through the list

You can conclude from the previous approach that we don’t actually need to store the nodes in the array as we only need the `length — n`th node.

So, we could say that the problem is simply reduced to: Remove the (Ln+1) th node from the beginning in the list, where L is the list length.

Solution Step
• Create a “dummy” node, which points to the list head.
• On the first pass, we find the list length L.
• Set a pointer to the dummy node and start to move it through the list until it comes to the `(L−n)th` node.
• Relink the `next` pointer of the `(L−n)th` node to the `(L−n+2)th` node.
Pseudo Code
``````ListNode removeNthFromEnd(ListNode head, int n) {
int end_index = 0
while(curr) {
end_index += 1
curr = curr->next;
}
index_to_remove = end_index - n
i = 0
ListNode prev = nullptr
while(i < index_to_remove) {
prev = curr
curr = curr.next
i += 1
}
}
else if(prev) {
prev.next = curr.next
}
delete curr
}``````
Complexity Analysis

Time complexity: O(L) where L is the length of the linked list.

Space complexity: O(1)

Critical Ideas to Think
• What information about the list does the first pass give us?
• What does the prev pointer represent here?
• Can you dry run the above pseudo code with the above examples?

#### 3. Making a single pass through the list

We could optimize the above approach where we only need a one-time traversal of the linked list. We could create two pointers, namely slow and a fast pointer pointing to the nodes that are n nodes apart from each other.

The fast pointer advances the list by n+1 steps from the beginning, while the slow pointer starts from the beginning of the list separating them by n nodes. We maintain this constant gap by advancing both pointers together until the fast pointer arrives past the last node. The slow pointer will be pointing at the nth 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 to the next node.

Solution steps
• Create a fast and slow pointer pointing to n-1th and 0th node of the linked list
• Start iterating over the linked list while updating the slow and fast pointers to its next.
• When the loop terminates, then the fast pointer would be pointing to the last node and slow would be pointing to n-1th from the last node.
• Set the next of slow pointer to its next of next
Pseudo Code
``````ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode dummy
ListNode slow = dummy
fast = fast.next
}
while(fast->next!=NULL){
slow = slow.next
fast = fast.next
}
//slow points to the node before target
slow->next = slow->next->next
return dummy->next
}``````
Complexity Analysis

Time complexity: O(L) where L is the length of the linked list.

Space complexity: O(1)

Critical Ideas to Think
• What did we initialize the fast and slow pointers with and why?
• How does the algorithm work if the given value of n is 1?
• Can you dry run this algorithm for the above example and point out the difference between the single pass and double pass algorithms?

#### Comparison of Different Solutions 