**Difficulty:** Medium, **Asked-in:** Amazon.

**Key takeaway:** An excellent problem for beginners to learn problem-solving with linked lists. This blog will guide you to work efficiently with linked lists and deal with pointers.

Write a program to remove the Nth node from the end of the linked list, i.e., when the node is traversed from the end, delete the Nth node from there.

Input: 1->2->3->4->5, N = 2, Output: 1->2->3->5.

Input: 7->8->4->5->3, N = 1, Output: 7->8->4->5.

- An iterative approach using double scan
- An iterative approach using two pointers

If M is the length of the linked list, then the Nth node from the end is the (M - N + 1)th node from the beginning. So we can modify the problem to remove the (M − N + 1)th node from the beginning of the list.

- Traverse the linked list and find the length M.
- Traverse the linked list again from the start until we reach the (M − N)th node.
- Now, we delete the (M - N + 1)th node and return the head pointer. Before deleting the node, we need to relink the next pointer of the (M - N)th node to the (M − N + 2)th node.

```
ListNode* removeNthNodeListEnd(ListNode* head, int N)
{
if (head == NULL || N <= 0)
return head;
int length = 0;
ListNode* curr = head;
while (curr != NULL)
{
length = length + 1;
curr = curr->next;
}
if (N > length)
{
cout << "Error: N is greater than the list length." << endl;
return head;
}
if (length == N)
{
temp = head->next;
delete head;
return temp;
}
ListNode* prev = NULL;
curr = head;
for (int i = 0; i < length - N; i = i + 1)
{
prev = curr;
curr = curr->next;
}
// Remove the Nth node
prev->next = curr->next;
delete curr;
return head;
}
```

```
def removeNthNodeListEnd(head, N):
if not head or N <= 0:
return head
length = 0
curr = head
while curr:
length = length + 1
curr = curr.next
if N > length:
print("Error: N is greater than the list length.")
return head
if length == N:
temp = head.next
del head
return temp
prev = None
curr = head
for i in range(length - N):
prev = curr
curr = curr.next
# Remove the Nth node
prev.next = curr.next
del curr
return head
```

```
ListNode removeNthNodeListEnd(ListNode head, int N)
{
if (head == null || N <= 0)
return head;
int length = 0;
ListNode curr = head;
while (curr != null)
{
length += 1;
curr = curr.next;
}
if (N > length)
{
System.out.println("Error: N is greater than the list length.");
return head;
}
if (length == N)
{
ListNode temp = head.next;
head.next = null;
return temp;
}
ListNode prev = null;
curr = head;
for (int i = 0; i < length - N; i = i + 1)
{
prev = curr;
curr = curr.next;
}
prev.next = curr.next;
curr.next = null;
return head;
}
```

We are performing two traversals of the linked list: first to calculate the length M of the list, and second to find the (M − N)th node. There are 2M − N operations, so the time complexity in the worst case is O(M). Space complexity is O(1), as we are using constant space.

The idea here is to use two pointers to find the (N + 1)th node from the end. In the beginning, the first pointer is at the (N + 1)th node from the start, and the second pointer is at the head of the linked list. By moving both pointers one step at a time until the first pointer reaches the end, the second pointer will point to the (N + 1)th node from the end, and we can easily remove the next node, which is the Nth node from the list end.

- We initialize two pointers: firstPointer and secondPointer. Initially, the secondPointer is positioned at the first node of the linked list, and the firstPointer is set to the (N + 1)th node from the beginning.
- Now, both pointers maintain a constant gap of N nodes. We advance them together until the firstPointer reaches the last node.
- At this point, the secondPointer points to the (N + 1)th node from the end. To remove the Nth node from the end of the list, we simply update the next pointer of the secondPointer to point to the next node's next pointer.

```
ListNode* removeNthNodeListEnd(ListNode* head, int N)
{
if (head == NULL)
return NULL;
ListNode* firstPointer = head;
ListNode* secondPointer = head;
for (int i = 1; i <= N; i = i + 1)
firstPointer = firstPointer->next;
if (firstPointer == NULL)
{
ListNode* temp = head->next;
head->next = NULL;
delete head;
return temp;
}
while (firstPointer->next)
{
firstPointer = firstPointer->next;
secondPointer = secondPointer->next;
}
ListNode* temp = secondPointer->next;
secondPointer->next = temp->next;
delete temp;
return head;
}
```

```
def removeNthNodeListEnd(head, N):
if not head:
return None
first_pointer = head
second_pointer = head
for i in range(N):
first_pointer = first_pointer.next
if not first_pointer:
temp = head.next
head.next = None
return temp
while first_pointer.next:
first_pointer = first_pointer.next
second_pointer = second_pointer.next
temp = second_pointer.next
second_pointer.next = temp.next
temp.next = None
return head
```

```
ListNode removeNthNodeListEnd(ListNode head, int N)
{
if (head == null)
return null;
ListNode firstPointer = head;
ListNode secondPointer = head;
for (int i = 1; i <= N; i++)
firstPointer = firstPointer.next;
if (firstPointer == null)
{
ListNode temp = head.next;
head.next = null;
return temp;
}
while (firstPointer.next != null)
{
firstPointer = firstPointer.next;
secondPointer = secondPointer.next;
}
ListNode temp = secondPointer.next;
secondPointer.next = temp.next;
temp.next = null;
return head;
}
```

If the length of the linked list is M, then the firstPointer will move M steps, and the secondPointer will move M - N steps. So, total pointer movement = 2M - N, and time complexity = O(M). Space complexity = O(1) as we are using constant space.

- What would be the best and worst-case scenarios for both approaches?
- Both algorithms take O(M) time, but which one performs fewer operations in the worst-case scenario?
- Sometimes, a "dummy" node is used to simplify certain corner cases, such as a list with only one node or removing the head of the list. In other words, having dummy nodes in any kind of linked list—whether singly, doubly, or circular—makes the corner cases vanish. Thus, programming becomes a lot easier. Now the critical question is: how do we use the idea of a dummy node in the above approaches to handle the corner cases?
- In the 2nd approach, we use two loops: one for taking the firstPointer to the (N + 1)th node and the other for finding the (N + 1)th node from the end. Can we merge these two processes and implement them using a single loop?
- Can we try to solve this problem using recursion?
- Can we implement the two-pointer solution differently?

- Iterative approach using double scan: Time = O(M), Space = O(1).
- Iterative approach using two pointers: Time = O(M), Space = O(1).

- Swap list nodes in pairs
- Remove every kth node of the linked list
- Delete all the nodes from the list that are greater than x
- Delete N nodes after M nodes of a linked list
- Detect a loop in a linked list
- Intersection point in Y-shaped linked lists

If you have any queries/doubts/feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!