Difficulty: Hard | Acceptance: 63.85% | Paid: No
Topics: Linked List, Recursion
- Examples
- Constraints
- Brute Force with Recursion
- Iterative with Stack
- Pointer Reversal
Examples
Input
head = [1,2,3,4,5], k = 2
Output
[2,1,4,3,5]
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 <= 5000
- 0 <= Node.val <= 1000
Brute Force with Recursion
Intuition
We can reverse the first k nodes and then recursively reverse the remaining list. If the remaining nodes are less than k, we will reverse them back.
Steps
- Count the total number of nodes in the list.
- If the count is less than k, return the head as it is.
- Otherwise, reverse the first k nodes of the list.
- Recursively call the reverseKGroup function for the rest of the list and attach it to the end of the reversed part.
- Ensure that the original order is preserved for any leftover nodes.
python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
count = 0
current = head
while current and count < k:
current = current.next
count += 1
if count < k:
return head
new_head = self.reverseFirstK(head, k)
head.next = self.reverseKGroup(current, k)
return new_head
def reverseFirstK(self, head, k):
prev = None
current = head
for _ in range(k):
next_node = current.next
current.next = prev
prev = current
current = next_node
return prevComplexity
- Time: O(n), where n is the number of nodes in the linked list.
- Space: O(n/k) due to the recursion stack, where each recursive call processes k nodes.
Iterative with Stack
Intuition
Use a stack to temporarily store k nodes, then pop them to reverse their order. This approach avoids recursion and handles reversal iteratively.
Steps
- Traverse the list in groups of k nodes.
- For each group, push nodes onto a stack until k nodes are reached.
- If k nodes are in the stack, pop them to reverse their order and connect them to the result list.
- If fewer than k nodes remain, leave them in their original order.
- Manage pointers carefully to ensure correct connections between reversed groups.
python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
dummy = ListNode(0)
dummy.next = head
prev_group_end = dummy
while True:
kth = self.getKth(prev_group_end, k)
if not kth:
break
next_group_start = kth.next
prev, curr = next_group_start, prev_group_end.next
while curr != next_group_start:
tmp = curr.next
curr.next = prev
prev = curr
curr = tmp
tmp = prev_group_end.next
prev_group_end.next = kth
prev_group_end = tmp
return dummy.next
def getKth(self, curr, k):
while curr and k > 0:
curr = curr.next
k -= 1
return currComplexity
- Time: O(n), where n is the number of nodes in the linked list.
- Space: O(1), as we only use a constant amount of extra space.
Pointer Reversal
Intuition
We can reverse the nodes in place by carefully manipulating pointers without additional data structures. This involves identifying groups, reversing them, and properly linking them back.
Steps
- Use a dummy node to simplify edge cases (like reversing from the head).
- For each group of k nodes, identify the start and end of the group.
- Reverse the nodes within the group by adjusting pointers.
- Connect the reversed group with the previous part of the list.
- Continue until all full groups of k nodes are processed.
python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
dummy = ListNode(0)
dummy.next = head
prev_group_end = dummy
while True:
kth = self.getKth(prev_group_end, k)
if not kth:
break
next_group_start = kth.next
prev, curr = next_group_start, prev_group_end.next
while curr != next_group_start:
tmp = curr.next
curr.next = prev
prev = curr
curr = tmp
tmp = prev_group_end.next
prev_group_end.next = kth
prev_group_end = tmp
return dummy.next
def getKth(self, curr, k):
while curr and k > 0:
curr = curr.next
k -= 1
return currComplexity
- Time: O(n), where n is the number of nodes in the linked list.
- Space: O(1), as we only use a constant amount of extra space.