Remove Nth Node From End of List - Python Solution

1. Introduction

"Remove Nth Node From End of List" is a classic problem dealing with linked lists. It tests one's ability to manipulate and traverse linked list structures, particularly in scenarios that require understanding the list's length and handling edge cases. This problem is common in interviews and competitive programming for testing basic linked list operations.

Problem

Given the head of a linked list, the task is to remove the nth node from the end of the list and return its head. This involves adjusting pointers within the list to bypass the targeted node.

2. Solution Steps

1. Initialize two pointers, start and end, at the head of the list.

2. Move end forward n times to create a gap of n nodes between start and end.

3. Traverse the list with both pointers until end reaches the last node.

4. Adjust the next pointer of start to skip the nth node from the end.

5. Handle edge cases, such as removing the first node.

6. Return the possibly updated head of the list.

3. Code Program

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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

    # Move end forward n steps
    for _ in range(n):
        end = end.next

    # Move both pointers until end reaches the last node
    while end.next:
        start = start.next
        end = end.next

    # Remove the nth node from the end
    start.next = start.next.next

    return dummy.next

# Example Usage
# Creating list for demonstration: [1 -> 2 -> 3 -> 4 -> 5]
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
result = removeNthFromEnd(head, 2)
# Output the list
output = []
while result:
    output.append(result.val)
    result = result.next
print(output)

Output:

[1, 2, 3, 5]

Explanation:

1. ListNode Class: The ListNode class represents each node in the linked list.

2. Dummy Node: A dummy node is used to simplify edge cases, like removing the first node.

3. Pointer Initialization: Two pointers, start and end, are used to create the gap of n nodes.

4. Traversing the List: The list is traversed while maintaining the gap until end is at the last node.

5. Node Removal: The nth node from the end is skipped by adjusting the next pointer of the start node.

6. Edge Cases Handling: The dummy node helps handle cases where the first node is removed.

7. Result: The function returns the head of the modified list after removing the nth node from the end.