Reverse Nodes in k-Group https://leetcode.com/problems/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 = 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