Problem Description
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]
My Idea
The idea here is to make use of several pointers: one for the first element before each group, one for the first element after each group and one for the k-th element(aka the last element of each group before reversal). The helper function getKth(curr, k) helps us assign the latter. Using these pointers we have the boundaries of each group, which allows us to utilize the algorithm from 206. Reverse Linked List for the reversal. They are also there to ensure we can link the groups back up after reversal, so we end up with one linked list. This yielded a time complexity of O(n).
My solution
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Time Complexity O(n)
def reverseKGroup(head: Optional[ListNode], k: int) -> Optional[ListNode]:
def getKth(curr,k):
while curr and k>0:
curr = curr.next
k-=1
return curr
res = ListNode(0,head)
groupPrev = res
kth = getKth(groupPrev, k)
while kth:
groupNext=kth.next
prev = kth.next
curr = groupPrev.next
while curr != groupNext:
next = curr.next
curr.next = prev
prev = curr
curr = next
temp = groupPrev.next
groupPrev.next = kth
groupPrev = temp
kth = getKth(groupPrev,k)
return res.next