Python solution with detailed explanation

  • 0


    Reverse Nodes in k-Group


    • Corner case: K > number of elements in the list. For example [1,2], 3. Do we need to have any special checks ? What if we simply add the list element at index k to sub-list k%K during the splitting phase? For this example, we will initialize an array of K=3 sub-lists. After adding the elements, we will have the third sub-list empty. If we traverse the first row from left to right, we will have the right answer. The next case teaches us how.
    • For k = 3, you should return: 3->2->1->4->5. Notice that while 1->2->3 is reversed, 4->5 is same an in order. How do we do this? During the combine phase, we add row by row from the sub-lists starting from the last sub-list. But for the last row, if the size of the row is less than K (like in this example it is 2), tails[-1] will be None. Use this to determine the order of traversal.
    class Solution(object):
        def reverseKGroup(self, head, K):
            :type head: ListNode
            :rtype: ListNode
            splits = [ListNode(-1) for _ in range(K)]
            tails = [splits[i] for i in range(K)]
            k = 0
            while head:
                temp =
                tails[k % K].next = head
                tails[k % K] = head
       = None
                head = temp
                k = k + 1
            start, tails = ListNode(-1), [splits[i].next for i in range(K)]
            result = start
            while k > 0:
                (s, e, inc) = (len(tails)-1,-1,-1) if tails[-1] else (0, len(tails), 1)
                for i in range(s, e, inc):
                    if tails[i] != None:
                        temp = tails[i].next
               = tails[i]
                        result = tails[i]
                        tails[i].next = None
                        tails[i] = temp
                        k -= 1

Log in to reply

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