DEV Community

Shahrouz Nikseresht
Shahrouz Nikseresht

Posted on

Day 60: Python Remove Nth Node From End of Linked List, Two-Pointer Magic to Delete in One Pass (LeetCode #19 Style)

#challenge #python #datastructures #leetcode

Welcome to Day 60 of the #80DaysOfChallenges journey! This intermediate challenge solves the iconic Remove Nth Node From End of Linked List problem (LeetCode #19), using a genius two-pointer technique to find and delete the target node in a single pass with O(1) extra space. It includes a Node class, builder for array-to-list conversion, printer for visualization, and main for interactivity, turning a tricky pointer problem into a complete, testable script. If you're crushing LeetCode, mastering linked lists, or prepping for interviews where "reverse or delete from end" is a staple, this "Python remove nth node from end" solution is elegant, efficient, and the exact method that impresses recruiters.

Example:

List 1→2→3→4→5, n=2 → 1→2→3→5 (remove 4, second from end)

💡 Key Takeaways from Day 60: Nth Node Removal Function

This task features a Node class for structure, builder and printer for usability, and the core removal with fast/slow pointers. It's a classic one-pass traversal: space fast n+1 ahead, move together to align slow before target. We'll detail: Node class and builder for list creation, removal with dummy and two pointers, and printer with main interactivity.

1. Node Class and Builder: Easy List Construction

The Node class sets up the structure:

class Node:
    """Simple singly linked list node."""
    def __init__(self, value: int):
        self.value = value
        self.next = None
Enter fullscreen mode Exit fullscreen mode

Basic with value and next.

The build_linked_list chains from array:

def build_linked_list(values: list[int]) -> Node:
    """Build a linked list from a list of integers."""
    if not values:
        return None

    head = Node(values[0])    # create the first node using the first element
    curr = head    # 'curr' will track the last node while building the list

    for v in values[1:]:      # iterate through the remaining values
        curr.next = Node(v)   # create a new node and attach it to the current one
        curr = curr.next      # move to the newly added node

    return head     # return the head of the constructed linked list
Enter fullscreen mode Exit fullscreen mode

O(n) build, handles empty.

2. Removal Function: Dummy Head and Two-Pointer Dance

The remove_nth_from_end uses dummy and pointers:

def remove_nth_from_end(head: Node, n: int) -> Node:
    """
    Remove the Nth node from the end using fast/slow pointers.
    Returns the new head after deletion.
    """
    dummy = Node(0)    # dummy node to simplify edge cases (like deleting head)
    dummy.next = head

    fast = dummy    # fast pointer
    slow = dummy    # slow pointer

    # Move fast pointer n+1 steps ahead
    for _ in range(n + 1):
        if fast is None:
            return head    # n is larger than list length
        fast = fast.next

    # Move both fast and slow together until fast hits the end
    while fast is not None:
        fast = fast.next
        slow = slow.next

    # slow is now just before the node to delete
    slow.next = slow.next.next

    return dummy.next    # new head of the list
Enter fullscreen mode Exit fullscreen mode

Dummy simplifies head deletion. Fast advances n+1, then both move, aligning slow before target. Skip next.next to delete. For 1→2→3→4→5, n=2: fast ends at None, slow at 2, skips 4. O(n) time.

3. Printer and Main: Visualization and Input

The print_linked_list shows structure:

def print_linked_list(head: Node) -> None:
    """Print linked list values cleanly."""
    curr = head    # start traversal from the head
    nodes = []    # store node values for formatted output

    while curr is not None:         # iterate until the end of the list
        nodes.append(str(curr.value))  # record current node's value
        curr = curr.next            # move to the next node

    print(f"Linked List: {' -> '.join(nodes)}")   # print values joined by arrows
Enter fullscreen mode Exit fullscreen mode

Arrow-joined print for "1 -> 2 -> 3".

Main processes input:

raw_nums = input("Enter list values (space-separated): ").strip()

raw_n = input("Enter n (which node from the end to remove): ").strip()

if raw_nums == "" or raw_n == "":
    print("Invalid input. Exiting.")
    return

nums = list(map(int, raw_nums.split()))

n = int(raw_n)

head = build_linked_list(nums)   
print(f"Original list:")
print_linked_list(head)

new_head = remove_nth_from_end(head, n)

print(f"List after removing {n}th node from the end:")

print_linked_list(new_head)
Enter fullscreen mode Exit fullscreen mode

Parses ints, builds, prints before/after. User-friendly.

🎯 Summary and Reflections

This nth removal showcases two-pointer brilliance for end access without length. It reinforced:

  • Dummy head utility: Handles edge deletions seamlessly.
  • Pointer spacing: Fast n+1 ahead aligns slow perfectly.
  • One-pass efficiency: O(n) time, no extra traversal.

Reflections: Recursion possible but iterative safer for long lists. Essential for list algos.

Advanced Alternatives: Recursive remove. Return dummy.next always. Your pointer trick? Share!

🚀 Next Steps and Resources

Day 60 nailed linked list deletions. In #80DaysOfChallenges? Tried recursion? Post!

Top comments (0)