## Similar Problems

Similar Problems not available

# Remove Nth Node From End Of List - Leetcode Solution

LeetCode: Remove Nth Node From End Of List Leetcode Solution

Difficulty: Medium

Topics: linked-list two-pointers

The problem "Remove Nth Node From End Of List" on LeetCode asks us to remove the n-th node from the end of a singly linked list and return the modified list. In other words, given a linked list and an integer n, we have to remove the node from the list that is n positions away from the end of the list.

The input to the problem is a linked list represented as a chain of nodes, where each node has two fields: a value field that contains the node's data, and a next field that contains a pointer to the next node in the list. The last node of the linked list has a next field that is NULL.

The output of the problem should be the modified linked list, where the n-th node from the end has been removed.

We can solve this problem using a two-pass algorithm, where in the first pass we count the total number of nodes in the list, and then in the second pass we remove the n-th node from the end of the list.

Here is the detailed solution using this algorithm:

- Initialize two pointers, current and temp, to the head of the linked list.
- Traverse the list using current pointer to count the number of nodes in the list. Let the count be N.
- Compute the position of the node to be removed as (N - n + 1), where n is the given input.
- If the position is 1, remove the head node and return the modified linked list.
- If the position is greater than 1, set the temp pointer to the node at position (position - 1).
- Set the next field of the node pointed to by temp to the node pointed to by the next field of temp.
- Return the modified linked list.

Here is the implementation of the above algorithm in Python:

```
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
# Step 1: Initialize pointers current and temp to the head of the linked list
current = head
temp = head
# Step 2: Traverse the list to count the number of nodes in the list
count = 0
while current:
count += 1
current = current.next
# Step 3: Compute the position of the node to be removed
position = count - n + 1
# Step 4: If the position is 1, remove the head node and return the modified linked list
if position == 1:
return head.next
# Step 5: If the position is greater than 1, set the temp pointer to the node at position (position - 1)
for i in range(position - 2):
temp = temp.next
# Step 6: Set the next field of the node pointed to by temp to the node pointed to by the next field of temp
temp.next = temp.next.next
# Step 7: Return the modified linked list
return head
```

The time complexity of this solution is O(n), where n is the number of nodes in the linked list, since we do a two-pass traversal of the list. The space complexity is O(1), since we use a constant amount of extra memory.

## Remove Nth Node From End Of List Solution Code

`1`