Skip to content

19. Remove Nth Node From End of ListΒΆ

Problem Link

To remove the \(n^{th}\) node from the end of the list in a single pass, we use a dummy node and two pointers, first and second. The dummy node simplifies edge cases, such as when the head node needs to be removed.

Both pointers start at the dummy node. We first move the second pointer forward by n nodes, creating a fixed gap of n between first and second.

Next, we move both pointers together until second reaches the last node. At this point, first points to the node just before the one that needs to be removed. We then skip the target node by updating first.next.

Finally, we return dummy.next as the new head of the modified list.

Runtime Complexity

Time: \(O(n)\)

Space: \(O(1)\)

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(val=0, next=head)
        first = second = dummy
        while second and n > 0:
            second = second.next
            n-=1

        while second.next:
            first = first.next
            second = second.next
        first.next = first.next.next
        return dummy.next

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Val: 0, Next: head}
    first, second := dummy, dummy
    for n > 0 && second != nil {
        second = second.Next
        n--
    }
    for second != nil && second.Next != nil {
        first = first.Next
        second = second.Next
    }
    first.Next = first.Next.Next
    return dummy.Next
}