Python (58 ms, beats 100%)


  • 0
    A
    #!/usr/bin/env python
    
    
    class Solution(object):
        def reverse(self, head, n):
            """
            Reverses the first n nodes of the list starting at the specified head
            node. Returns a tuple (a, b, c) where a and b are the start and end of
            the reversed list. c is the length of the reversed portion of the list.
            """
            assert n > 0
            assert head is not None
    
            tail = head
            current = head.next
            length = n
            n -= 1
    
            # Reverse the list by going through it in forward order and prepending
            # each node to the front.
            while n > 0 and current is not None:
                next = current.next
                current.next = head
                head = current
                current = next
                n -= 1
    
            # Ensure the tail of the reversed list points to the next element.
            tail.next = current
            return (head, tail, length - n)
    
        def reverseKGroup(self, head, k):
            """
            Reverses the list starting at the head node k nodes at a time. If the
            list length is not a multiple of k the trailing nodes at the end must
            remain in their original order.
            """
            sentinel = ListNode(None)
            sentinel.next = head
            current = sentinel
    
            while current is not None and current.next is not None:
                sublist = self.reverse(current.next, k)
                # Check if this is a trailing list with less than k nodes.
                if sublist[2] != k:
                    # Reverse the list again to bring it back into original order.
                    sublist = self.reverse(sublist[0], k)
                current.next = sublist[0]
                current = sublist[1]
    
            return sentinel.next
    

  • 0
    J

    I've just copied and submitted your code and I've got 116ms....
    Perhaps the runtime on the server is not comparable for different users.^^


Log in to reply
 

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