Simple Python beats 99%

  • 0
    class Solution(object):
        def reverseKGroup(self, head, k):
            :type head: ListNode
            :type k: int
            :rtype: ListNode
            if k<=1: return head # will not change the list if k<=1
            # create a dummy node in the beginning so that it would be easy to handle the nodes in the beginning
            start = ListNode(0)
   = head
            dummy = start 
            # will store k nodes
            temp = []
            while start:      # if current node is not None
                temp = []     # clear the array
                for i in range(k):        # if the node is not None, add it to the list. 
                    if not head: break
                    head =
                if len(temp) != k:     # if there is not enough nodes, link the first one to the last processed node. don't change the rest links
           = temp[0] if len(temp)>0 else None
                for i in range(k-1,-1,-1):      # reverse the array, link the nodes one by one
           = temp[i]
                    start =

  • 0

    But I wonder whether O(k) space is valid

  • 0

    Here comes the new version to get rid of the array. Beat 100%...

    class Solution(object):
        def reverseKGroup(self, head, k):
            if k<=1: return head
            # use dummy as well
            start = ListNode(0)
   = head
            dummy = start
            # mark the last node of k nodes (end is the actually)
            end = head
            while start:    # if start node is not None
                count = 0
                while end and count < k:   # looking for the last node
                    count += 1
                    end =
                if count != k: break  # not enough nodes, just leave them there
                #handle the k nodes between start and end (not included)
                afterStart =  # the will be the last one of the new group
                temp =  # temp is starting from the second node of the group
                last = afterStart  # last is the node before temp node
                for i in range(k-2):   # re-link the nodes in the group
                    n =
           = last
                    last, temp = temp, n
                # now the group is almost reversed. Handle the rest
       = last    # link the last node and the one before it
       = end    # link the afterStart node to the rest nodes
       = temp    # link start node to the first of the group
                start = afterStart     # move the start node, which is the one before the next group

Log in to reply

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