Remove Nth Node from End of List

How to Solve Remove Nth Node from End of List

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 = [1], n = 1

Output: []

Example 3

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

Output: [1]

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.

Python Implementation

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

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