1. Problem Statement (Simple Explanation):
You’re given the head of a singly linked list and an integer k.
You must:
Reverse the nodes of the list k at a time.
If the number of nodes at the end is less than k, leave that tail part as is (not reversed).
You must not modify node values, only relink nodes.
Return the head of the modified list.
2. Examples:
Example 1:
Input: head = [1,2,3,4,5], k = 2
Process in groups of 2:
Group 1: [1,2] → [2,1]
Group 2: [3,4] → [4,3]
Remaining node: [5] (less than k) → unchanged
Output: [2,1,4,3,5]
Example 2:
Input: head = [1,2,3,4,5], k = 3
Process in groups of 3:
Group 1: [1,2,3] → [3,2,1]
Remaining nodes: [4,5] (less than k) → unchanged
Output: [3,2,1,4,5]
Constraints:
Number of nodes = n
1 <= k <= n <= 500
0 <= Node.val <= 10000
Follow-up: Solve using O(1) extra space (i.e., in-place, no extra data structures other than a few pointers).
3. Approach – Iterative In-place Reversal in k-Size Groups:
We must reverse nodes in chunks of size k while maintaining links between groups.
High-Level Idea:
Use a dummy node before the head to simplify pointer handling.
Process the list in groups of size k:
Find the k-th node starting from the current group’s previous node.
If fewer than k nodes remain → stop.
Reverse the k nodes between groupPrev.next and kth.
Connect the reversed block back to the list.
Move to the next group and repeat.
This works in one pass, reversing in-place with constant extra space.
Key Pointer Roles:
dummy: node before the head.
groupPrev: node before the current group to reverse.
kth: the k-th node ahead from groupPrev (end of the group).
groupNext: kth.next (start of the next group after the current one).
Within each group:
reverse the segment [groupPrev.next, ..., kth].
Helper: Find k-th Node From groupPrev:
Reversing One Group:
Suppose:
groupPrev -> a -> b -> c -> groupNext
(head of group) (kth.next)
After reversing group [a,b,c]:
groupPrev -> c -> b -> a -> groupNext
Process:
prev = groupNext (so tail connects correctly).
curr = groupPrev.next (head of group before reversing).
While curr != groupNext:
tmp = curr.next
curr.next = prev
prev = curr
curr = tmp
After this, prev is the new head of the group (old kth).
Old head groupPrev.next becomes the tail of the group.
Connect:
tail = groupPrev.next
groupPrev.next = prev
groupPrev = tail for the next iteration.
Pseudo-code (Iterative, O(1) Extra Space):
This is in-place and uses only a fixed number of extra pointers - O(1) extra space.
Complexity:
Let n be number of nodes:
Each node is visited and relinked a constant number of times.
Time: O(n)
Extra space: O(1) (follow-up satisfied).
4. Java code:
6. C++ code:
7. Python code:
8. JavaScript code:
Comments
Post a Comment