25. Reverse Nodes in k-Group
Explanation
To solve this problem, we can iterate through the linked list in groups of size k. For each group, we reverse the nodes in the group. We maintain three pointers: prev, curr, and next to reverse the nodes in each group. After reversing the group of nodes, we update the pointers accordingly. We repeat this process until we reach the end of the linked list. If the remaining nodes are less than k, we leave them as they are.
Time Complexity: O(n) where n is the number of nodes in the linked list. Space Complexity: O(1)
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || k == 1) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
while (head != null) {
ListNode tail = prev;
for (int i = 0; i < k; i++) {
tail = tail.next;
if (tail == null) return dummy.next;
}
ListNode next = tail.next;
ListNode[] reversed = reverseList(head, tail);
head = reversed[0];
tail = reversed[1];
prev.next = head;
tail.next = next;
prev = tail;
head = next;
}
return dummy.next;
}
private ListNode[] reverseList(ListNode head, ListNode tail) {
ListNode prev = tail.next;
ListNode curr = head;
while (prev != tail) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return new ListNode[]{tail, head};
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.