Problem Description
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.
Follow up:
- Could you solve the problem in
O(1)extra memory space? - You may not alter the values in the list's nodes, only nodes itself may be changed.
Example 1:
Input: head = [1,2,3,4,5], k = 2 Output: [2,1,4,3,5]
Example 2:
Input: head = [1,2,3,4,5], k = 3 Output: [3,2,1,4,5]
Example 3:
Input: head = [1,2,3,4,5], k = 1 Output: [1,2,3,4,5]
Example 4:
Input: head = [1], k = 1 Output: [1]
Constraints:
- The number of nodes in the list is in the range
sz. 1 <= sz <= 50000 <= Node.val <= 10001 <= k <= sz
The description was taken from https://leetcode.com/problems/reverse-nodes-in-k-group/.
Problem Solution
#O(N) Time, O(1) Spaceclass Solution: def reverseKGroup(self, head: ListNode, k: int) -> ListNode: dummy = ListNode(0, head) previous_group = dummy kth_node = self.get_kth_node(previous_group, k) while kth_node: next_group = kth_node.next pointer_one, pointer_two = kth_node.next, previous_group.next while pointer_two != next_group: pointer_three = pointer_two.next pointer_two.next = pointer_one pointer_one = pointer_two pointer_two = pointer_three sublist_head = previous_group.next previous_group.next = kth_node previous_group = sublist_head kth_node = self.get_kth_node(previous_group, k) return dummy.next def get_kth_node(self, current: ListNode, k: int) -> ListNode: while current and k > 0: current = current.next k -= 1 return currentProblem Explanation
This problem is a combination of Swap Nodes in Pairs and Reverse Linked List II.
We can solve this problem by continuously traversing the linked list and counting ahead to k nodes and isolate a sublist partition that will be reversed.
In-place swaps or reversals of linked lists will typically come down to a few tasks:
-
Saving a reference to the node of the next iteration
-
Redirecting
.nextpointers
-
Iterating to the previously saved node references
Just like we need to save reference nodes of the pointers we need to swap, we will also need to set them for the nodes each sublist has to reconnect with after reversing it, that is the main trick of this problem.
Let's start by creating the helper function that will send a pointer ahead of our current spot in the linked list and return which node is k nodes ahead of us.
This function will take a current node, a k value, and it will return the kth node.
def get_kth_node(self, current: ListNode, k: int) -> ListNode:
While the current node is not at a null value and while k is greater than zero, we will continue to iterate to the next node and decrement k.
while current and k > 0: current = current.next k -= 1
When the loop breaks, that means either the current pointer has reached the kth node, or it has reached a null node. This is how we will know if we have stumbled upon a group of nodes that has a size less than k if our function returns null.
return current
Now let's create a dummy head node so that we don't have to reverse the first group prior to our traversal.
This is also an easy method to avoid having to fix connection pointers to the actual head when it gets reversed.
dummy = ListNode(0, head)
Next, we will set a previous_group pointer so that we can know what the last node of the previous group was for connection purposes after reversing a new sublist group.
It will be set to the dummy head node initially.
previous_group = dummy
Now that we have our helper function built, we can use it to get the kth node and begin reversing the group of nodes between the node directly after the previous group and the kth node.
We will pass the dummy head as the current previous group and our input k value.
kth_node = self.get_kth_node(previous_group, k)
Now we will get into the meat and potatoes of our solution.
While the kth node is not null, we still have a group of nodes that are of size k and we will continue reversing them.
while kth_node:
Before we begin overwriting pointers, we will want to save the first node of the next group so that we still have a reference of where we are iterating to and also where we need to point the far-right node of our current iteration to.
next_group = kth_node.next
Okay, now we will start our reversal, we will do this with three pointers.
Let's set the first pointer to the first node of the next group, and the second pointer to the first node of the current group.
It may be more helpful to some to rename these three pointers to "prev", "curr", and "next_node", but this may get confusing after the sublist reversal is finished.
pointer_one, pointer_two = kth_node.next, previous_group.nex
While our second pointer isn't at the next group yet, we still have nodes to reverse.
while pointer_two != next_group:
The last pointer we need to set is the third.
This is the node pointer two is connected to, and since we are about to overwrite the node of pointer two, we will need to know which node to iterate to at the end of the loop.
pointer_three = pointer_two.next
Let's draw out what this swapping of pointers is going to look like on an input of [1,2,3,4,5,6] and a k of three.
We'll set our pointers accordingly to begin reversing the first group of three nodes after the dummy head.
Node one will now point to node four.
pointer_two.next = pointer_oneThis is going to cause both node one and node three to point to node four. We just broke our reference to node two and we now have two heads, the dummy head, one, and the new head, two.
pointer_one = pointer_two pointer_two = pointer_threeNode two will now point to node one.
Our pointers are wacky right now. We have nothing pointing to node three, and two nodes pointing to node one. We have three heads now, we will clean this up later.
Pointer two is now in the next group, break from the loop.
This group has been reversed.
Now that we have reversed a group, we need to fix the group's connections to the rest of the list.
The list went from:
0->1->2->3->4->5->6
to:
We need to fix the connection between the previous group and the current group.
The last node of our current group was initially the first node.
3->2->1->4->5->6->None
sublist_head = previous_group.next
The first node of the current group was initially the last node, so we will fix that connection here.
3->2->1->4->5->6->None
previous_group.next = kth_node
0->3->2->1->4->5->6->None
After we are done with a group reversal, we will set the previous_group to the last node of the current group we just reversed, this would be node one.
This will effectively move us forward down the list.
previous_group = sublist_head
Afterward, we will get the next k value and continue our reversals.
kth_node = self.get_kth_node(previous_group, k)
When the loop has broken, that means we have gotten to a null value which means that all of the groups have been reversed, or the last group was less than k and doesn't need to be reversed.
When that happens, we will return the list after the dummy head as that node would be the actual head.
return dummy.next