← all entries
A-045● Day 452026.06.20hardleetcode #25neetcode150

Reverse Nodes in k-Group

#linked-list#recursion
↗ leetcode #25 · reverse-nodes-in-k-group
01

Problem

· problem
P.045

Reverse Nodes in k-Group

↗ leetcode #25

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.

constraints
  • · The number of nodes in the list is n
  • · 1 ≤ k ≤ n ≤ 5000
  • · 0 ≤ Node.val ≤ 1000
// paraphrased summary — see source for full text
examples
example 1input → output
[1,2,3,4,5]
2
[2,1,4,3,5]
example 2input → output
[1,2,3,4,5]
3
[3,2,1,4,5]
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    What happens if fewer than k nodes remain at the end?
  • ☐
    Can we modify the node values?
  • ☐
    Why do we use a dummy node?
  • ☐
    Why must we find the k-th node in every iteration?
  • ☐
    Why not reverse the entire list first and then re-arrange?
  • ☐
    Can we solve this recursively?
  • ☐
    Should we copy node values into new nodes?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Initialize dummy node
○
dummy = ListNode(0, head)
○
dummy = ListNode(head)
○
dummy = head
step 2· Locate the k-th node from current position│ nested
○
kth = self.getKth(groupPrev, k)
○
kth = self.getKth(groupPrev.next, k)
○
kth = self.getKth(head, k)
step 3· Check if k nodes exist in current group│ nested
○
if not kth:
○
if not kth.next:
○
if not groupPrev:
step 4· Reverse pointers within the k-group│ nested
○
prev, curr = kth.next, groupPrev.next
○
prev, curr = groupPrev.next, kth.next
○
prev, curr = None, groupPrev.next
step 5· Reconnect reversed group to the list│ nested
○
tmp = groupPrev.next
○
groupPrev.next = groupNext
○
groupPrev = kth
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
class Solution:
2
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
3
        dummy = ListNode(0, head)
4
        groupPrev = dummy
5
6
        while True:
7
            kth = self.getKth(groupPrev, k)
8
            if not kth:
9
                break
10
            groupNext = kth.next
11
12
            # reverse group
13
            prev, curr = kth.next, groupPrev.next
14
            while curr != groupNext:
15
                tmp = curr.next
16
                curr.next = prev
17
                prev = curr
18
                curr = tmp
19
20
            tmp = groupPrev.next
21
            groupPrev.next = kth
22
            groupPrev = tmp
23
        return dummy.next
24
25
    def getKth(self, curr, k):
26
        while curr and k > 0:
27
            curr = curr.next
28
            k -= 1
29
        return curr
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
[1,2,3,4,5]
2
→
[2,1,4,3,5]
case 2
[1,2,3,4,5]
3
→
[3,2,1,4,5]
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.