## Remove Nth Node From End of List

Difficulty: Medium

Asked in: Google, Amazon

#### 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

**Using Auxillary Space**— By saving each node in an array**Making two passes through the list**— remove the`length- nth`

from the beginning.**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[]
ListNode curr = head
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 {
head = list[1]
}
return head
}
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
`(`

node.*L*−*n*)th - Relink the
`next`

pointer of the`(`

node to the*L*−*n*)th`(`

node.*L*−*n*+2)th

Pseudo Code

```
ListNode removeNthFromEnd(ListNode head, int n) {
ListNode curr = head
int end_index = 0
while(curr) {
end_index += 1
curr = curr->next;
}
index_to_remove = end_index - n
i = 0
curr = head
ListNode prev = nullptr
while(i < index_to_remove) {
prev = curr
curr = curr.next
i += 1
}
if(curr == head) {
head = head.next
}
else if(prev) {
prev.next = curr.next
}
delete curr
return head
}
```

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
- Now return the head.

Pseudo Code

```
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode fast = head
ListNode dummy
dummy->next = head
ListNode slow = dummy
int step_ahead = 0
while(step_ahead < n-1){
fast = fast.next
step_ahead += 1
}
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

#### Suggested problems to Solve

- K reverse linked list
- Reverse a Link List
- Delete a Doubly Linked List node at a given position
- Recursively delete a kth node from a linked list

If you have any more approaches or you find an error/bug in the above solutions, please comment down below.

**Happy Coding! Enjoy Algorithms!**