19. Remove Nth Node From End of List (Python)

Related Topic

Linked-List. Two-Pointers.

Description

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

Sample I/O

Example 1

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note

Given n will always be valid.

Follow Up

Could you do this in one pass?

Methodology

First We need to confirm that if Linked List is signly or doubly and if the n is valid or not.

The straight forward solution is iterate the linked list to get the size, then calculate the stop point which is stop = size - n. After that, we iterate the linked list again (here we need a dummy node or sometimes call dummy head) until reach the stop point and move the current node pointer to its’ next next node. Finaly we will get the new linked list. This solution works but it did not apply for one pass.

For one pass solution, we create two pointers slow and fast, move the fast pointer n step ahead to slow pointer then we start to move both pointer until the fast pointer reach to the end and at this moment, the slow pointer stop at the node whose next node need to be removed. We simply change the slow pointer node’s next pointer to its next’s next node. This is much faster since we do not need to iterate the linked list twice.

Code (straight forward solution)

def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        size = 0
        new_head = dummy_head = head
        while head:
            size+=1
            head = head.next
        stop = size - n
        if stop == 0: return new_head.next
        counter = 1
        while dummy_head:
            if counter == stop:
                dummy_head.next = dummy_head.next.next
                return new_head
            counter+=1
            dummy_head = dummy_head.next

BigO

Iterate the linked list twice, so total time complexity is O(2n)

Code (one pass solution)

def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        fast = slow = head
        for _ in range(n):
            fast = fast.next
        if not fast:
            return head.next
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return head

BigO

Iterate the linked list once, so total time complexity is O(n)