25. Reverse Nodes in k-Group — LeetCode(Python)
I got you!
Problem:
Given the head of a linked list, reverse the nodes of the list k at a time, and return the 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.
You may not alter the values in the list’s nodes, only nodes themselves 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]Constraints:
- The number of nodes in the list is
n. 1 <= k <= n <= 50000 <= Node.val <= 1000
Follow-up: Can you solve the problem in O(1) extra memory space?
Solution:
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
groupPrev = dummy
while True:
kth = self.getkth(groupPrev, k)
if not kth: #if less than k nodes are remaining in the list
break
groupNext = kth.next
#reverse group
prev, curr = kth.next, groupPrev.next
while curr != groupNext:
temp = curr.next
curr.next =prev
prev = curr
curr = temp tmp = groupPrev.next
groupPrev.next = kth
groupPrev = tmp
return dummy.nextdef getkth(self, curr, k):
while curr and k:
curr = curr.next
k -= 1
return curr
Explanation —
We use a dummy node here to save ourselves some time by not having to think of edge cases that might arise.
We are asked to reverse k nodes at a time.
So first, we reach the kth node from the start. We set our groupNext pointer to the (k+1)th node.
We now reverse the next k nodes.
After doing so, we make our groupPrev pointer to point to the kth node and shift it to the right, using a temporary variable.
Finally, we return the head of the new linked list which is where our dummy node is pointing at.
Time and Space Complexity —
Since we are iterating over all nodes in the linked list atmost twice, we can say that our algorithms runs in linear time.
Also, we require a constant amount of extra space.
Thus, if n is the length of the linked list,
Time Complexity: O(n)
Space Complexity: O(1)
