LeetCode 25. Reverse Nodes in k-Group

November 19, 2024

I had difficulties with this problem with terminating completed lists. I was surprised that ChatGPT didn't give this simple solution, it suggested a large rework. I'll have to be mindful before implementing all of ChatGPT's suggestions.

Solution

1# Definition for singly-linked list.
2# class ListNode:
3#     def __init__(self, val=0, next=None):
4#         self.val = val
5#         self.next = next
6class Solution:
7    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
8        batch = []
9        start = None
10        curr = None
11        while head:
12            batch.append(head)
13            head = head.next
14            if len(batch) == k:
15                if curr:
16                    curr.next = batch.pop()
17                    curr = curr.next
18                else:
19                    curr = batch.pop()
20                    if not start:
21                        start = curr
22                     
23                while batch:
24                    curr.next = batch.pop()
25                    curr = curr.next
26                
27        if batch and curr:
28            curr.next = batch[0]
29        elif batch:
30            start = batch[0]
31        elif not batch and curr:
32            curr.next = None
33        
34        return start

Time complexity is O(n) = n and space complexity is O(k).

LeetCode 92. Reverse Linked List II

LeetCode 100. Same Tree