unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 19: Remove Nth Node From End of List

link

As long as we know the previous and the next nodes of the to-be-deleted node, we can update the pointers to delete the node.

Say there are total N nodes in the list. Say the n-th node from the end is the m-th node from the head. Then, m+n = N+1 and m = N-n+1. From the head, if we jump N-n times, we would reach the n-th node from the end. We also move the prev pointer to facilitate delete.

Time: \mathcal{O}(n), space: \mathcal{O}(1).

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        def get_list_length(head: ListNode) -> int:
            node_count = 0
            t = head
            while t:
                node_count += 1
                t = t.next
            return node_count
 
        node_count = get_list_length(head)
         
        dummy = ListNode(next=head)
        prev, curr = dummy, head
        jump_count = node_count - n
        while jump_count > 0:
            prev = curr
            curr = curr.next
            jump_count -= 1
         
        prev.next = curr.next
        return dummy.next

Finding the length of the list takes one extra scan. We could do the finding and deleting in a single scan. There are n nodes from the to-be-deleted node to the last list node.

So, we start with a current pointer at the head and a forward pointer at the n-th node from the head. We then move both pointers together. When the forward pointer reaches the last list node, the current pointer is at the to-be-delete node. We also track a previous pointer to facilitate delete.

Time: \mathcal{O}(n), space: \mathcal{O}(1).

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        previous, current = dummy, head

        forward, jump = head, n-1
        while jump > 0:
            forward = forward.next
            jump -= 1
        
        while forward.next:
            previous = current
            current = current.next
            forward = forward.next
        
        previous.next = current.next
        return dummy.next

The dummy node simplifies the logic but isn’t essential.

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        previous, current = head, head

        forward, jump = head, n-1
        while jump > 0:
            forward = forward.next
            jump -= 1
        
        while forward.next:
            previous = current
            current = current.next
            forward = forward.next

        if current == head:
            return head.next
        
        previous.next = current.next
        return head

tanvirdotzaman

Leave a comment