Pages

108 Remove N-th Node From End (Two pointers to remove target node)

 

Approach: Two-Pointer (Normal, 2-pass method)

     Idea:

  1. First, traverse the entire list to find the length.

  2. Then, calculate the (length - n) position from the start.

  3. Traverse again to the (length - n - 1)-th node (the node before the one to delete).

  4. Delete the N-th node from the end.



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

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

    # Step 1: Find the length
    length = 0
    current = head
    while current:
        length += 1
        current = current.next

    # Step 2: Find (length - n)-th node
    current = dummy
    for _ in range(length - n):
        current = current.next

    # Step 3: Delete the node
    current.next = current.next.next

    return dummy.next
Tags