Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5 For k = 3, you should return: 3->2->1->4->5
We will need to iterate through the linked list k at a time. We will use : … 4 -> 5 -> 6 -> 7 -> 8 -> … k = 3, and the group starts at 5 as an example
- If we hit null before we got group of size k, we will not do anything.
- Else we go to 3
- Get the pointer to the node right before the beginning of the first node in group. let’s call it prev_ptr. In our example, we need to keep a pointer to 4.
- Get the pointer to the current node, cur_ptr. In our example, a pointer to 5.
- Reverse the linked list starting from current pointer ( in our case it is a pointer to 5), till k node after.
- Get the pointer to the first node in the reversed linked list, new_head. It should be returned by the reverse routine.
- Point prev_ptr to new_head and cur_ptr.next to Null
- Call this function again with head = curr.next
A refined and more concise general idea
While we have size k group :
- Move forward k group to find the head of next group ( might be less than k)
- Reverse size k linked list from head
- Connect the two groups
def reverseKGroup(self, head, k): dummy = jump = ListNode(0) dummy.next = l = r = head while True: count = 0 while r and count < k: # use r to locate the range r = r.next count += 1 if count == k: # if size k satisfied, reverse the inner linked list pre, cur = r, l for _ in range(k): next_node = cur.next cur.next = pre pre = cur cur = next_node jump.next, jump, l = pre, l, r # connect two k-groups #print(jump.next.val, jump.val, l.val) else: return dummy.next
The outer while loop will be terminated when the number of remaining nodes starting from r is fewer than k.
After the while loop that move r forward, r will point at the head of next group.
At the end of for loop, pre will contain the tail of the last group. Since the group is reversed, pre will contain the head of the reversed list.
jump is the tail of the old group. We will point jump.next it at the head of the next group, which is pre.
In the next iteration, the tail of the previous reversed group is the head of the previous unreversed group. So we point jump at l at each round.