## DEV Community is a community of 667,450 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# LeetCode Remove Nth Node From End of List Alkesh Ghorpade
Ruby on Rails and Golang consultant

### Problem statement

Given the head of a linked list, remove the nth node from the end of the list

Example 1:

``````Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
``````

Example 2:

``````Input: head = , n = 1
Output: []
``````

Example 3:

``````Input: head = [1,2], n = 1
Output: 
``````

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

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

- 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

``````
##### C++ solution
``````class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* fast;
ListNode* slow;

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

if(fast == NULL){
}

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

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

}
};
``````
##### Golang solution
``````func removeNthFromEnd(head *ListNode, n int) *ListNode {
node := &ListNode{}

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) {

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

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

slow.next = slow.next.next;

};
``````

Let's dry-run our algorithm.

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

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 