## 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 ( L n +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 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 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 