Python concise one-pass solution with dummy head.


  • 4
    C
    def removeNthFromEnd(self, head, n):
        dummy = ListNode(0)
        dummy.next = head
        fast = slow = dummy
        for _ in xrange(n):
            fast = fast.next
        while fast and fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy.next

  • 0
    Y
    This post is deleted!

  • 0
    R

    But it's still like to go a two-pass: one pass for 'fast' and another for 'slow'. What I did is to use a dict, which seems to go only one-pass.


  • 0
    C

    If you use dict then you will spend extra space. Here fast and slow poniters will move forward in the same pass, so it is one-pass, just as using fast-slow pointers to find the middle point of a linked list.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.