Python solution with detailed explanation


  • 0
    G

    Solution

    Reverse Nodes in k-Group https://leetcode.com/problems/reverse-nodes-in-k-group/

    Algorithm

    • https://discuss.leetcode.com/topic/75958/python-solution-with-detailed-explanation
    • 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.
    • https://goo.gl/photos/JtD8rwr8dG9xVita7
    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 = head.next
                tails[k % K].next = head
                tails[k % K] = head
                head.next = 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
                        result.next = tails[i]
                        result = tails[i]
                        tails[i].next = None
                        tails[i] = temp
                        k -= 1
            return start.next
    

Log in to reply
 

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