We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Remove Nth Node From End of List

Difficulty: Medium

Problem Description

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

Key Insights

  • The problem requires removing a specific node identified by its position from the end of the linked list.
  • A two-pointer technique can be utilized to find the n-th node from the end in a single pass.
  • Edge cases include lists with only one node and when n equals the size of the list.

Space and Time Complexity

Time Complexity: O(sz), where sz is the number of nodes in the linked list (since we may traverse the list). Space Complexity: O(1), as we are using a constant amount of space regardless of the input size.

Solution

The solution employs a two-pointer approach. The idea is to create a gap of 'n' nodes between two pointers. The first pointer is moved 'n' steps ahead, and then both pointers are moved simultaneously until the first pointer reaches the end. At that point, the second pointer will be positioned just before the n-th node from the end, allowing us to easily remove it.

  1. Initialize two pointers, first and second, both pointing to the head of the list.
  2. Move the first pointer n nodes ahead.
  3. Then, move both pointers one node at a time until first reaches the end of the list.
  4. At this point, second will be pointing to the node just before the node to be removed.
  5. Adjust the next pointer of second to skip the node to be removed.
  6. Finally, return the head of the modified list.

Code Solutions

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

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    # Create a dummy node that points to the head
    dummy = ListNode(0, head)
    first = dummy
    second = dummy
    
    # Move first n+1 steps ahead so that there's a gap of n nodes
    for _ in range(n + 1):
        first = first.next
    
    # Move both pointers until first reaches the end
    while first:
        first = first.next
        second = second.next
    
    # Remove the n-th node from end
    second.next = second.next.next
    
    return dummy.next  # Return the new head
← Back to All Questions