Simple Python beats 99%


  • 0
    M
    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)
            start.next = 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
                    temp.append(head)
                    head = head.next
                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
                    start.next = temp[0] if len(temp)>0 else None
                    break
                for i in range(k-1,-1,-1):      # reverse the array, link the nodes one by one
                    start.next = temp[i]
                    start = start.next
            return dummy.next
    

  • 0
    M

    But I wonder whether O(k) space is valid


  • 0
    M

    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)
            start.next = head
            dummy = start
    
            # mark the last node of k nodes (end is the last.next 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 = end.next
                if count != k: break  # not enough nodes, just leave them there
    
                #handle the k nodes between start and end (not included)
                afterStart = start.next  # the start.next will be the last one of the new group
                temp = afterStart.next  # 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 = temp.next
                    temp.next = last
                    last, temp = temp, n
                
                # now the group is almost reversed. Handle the rest
                temp.next = last    # link the last node and the one before it
                afterStart.next = end    # link the afterStart node to the rest nodes
                start.next = temp    # link start node to the first of the group
                start = afterStart     # move the start node, which is the one before the next group
            return dummy.next 
    

Log in to reply
 

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