MEDIUM
DATA STRUCTURES AND ALGORITHMS

# How to Solve Remove Nth Node from End of List

Written By ## Remove Nth Node from End of List Introduction

Remove Nth Node from End of List problem as the name implies asks us given the head of a linked list and a value N, remove the Nth node from the end of the list, and return its head. This problem can be solved simply in one traversal by using two pointers, a fast and a slow pointer.

## Remove Nth Node from End of List Problem

Given the head of a linked list, remove the nth node from the end of the list and return its head.

### Example Inputs and Outputs

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

## Remove Nth Node from End of List Solutions

To solve this problem, we can use a two-pointer approach. We'll initialize two pointers, fast and slow, both pointing to the head of the linked list. We'll move the fast pointer n steps ahead, creating a gap of n nodes between fast and slow. Then, we'll move both pointers simultaneously until the fast pointer reaches the end of the linked list.

At this point, the slow pointer will be pointing to the nth node from the end. To remove this node, we'll adjust the next pointers accordingly. If the node to be removed is the head itself, we'll update the head to the next node. Otherwise, we'll set the slow.next pointer to skip the nth node and point to the next node.

``````def removeNthFromEnd(head, n):
dummy = ListNode(0)

fast = slow = dummy

# Move fast pointer n steps ahead
for _ in range(n):
fast = fast.next

# Move both pointers simultaneously until fast reaches the end
while fast.next:
fast = fast.next
slow = slow.next

# Remove the nth node by adjusting the next pointers
slow.next = slow.next.next

return dummy.next``````

#### Time/Space Complexity Analysis

• Time Complexity: O(N), where N is the length of the linked list, as we only iterate through the list once.
• Space Complexity: O(1), as we are using a constant amount of extra space for the two pointers and the dummy node.