Question
Given a linked list, reverse the nodes of a linked list k at a time and return its modified 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 nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
Stats
| Frequency | 2 |
| Difficulty | 4 |
| Adjusted Difficulty | 4 |
| Time to use | ---------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Analysis
The problem is solved in 2 steps. First, get the next k-group. If remaining items is less than k, terminate the program. Otherwise, reserve this k-group and keep going.
To solve this question is very tricky. We need to be clear about this: 4 nodes need to be kept track of: 2 elements before and after the k-group, and 2 elements within the k-group.
The difficult point is while and after reverse the k-group, how to maintain the ‘pre’ node and future ‘pre’ node correctly.
Solution
Use Linkedlist Template from NineChap to solve.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (k <= 1 || head == null) {
return head;
}
ListNode nextGroup = head;
for (int i = 0; i < k; i++) {
if (nextGroup == null) {
// there isn't k nodes in this list
return head;
}
nextGroup = nextGroup.next;
}
// now we're sure the list have at least k nodes
// reverse this list (by re-connecting the next pointer k times)
ListNode newHead = head;
ListNode tail = null;
for (int i = 0; i < k; i++) {
ListNode temp = newHead.next;
newHead.next = tail;
tail = newHead;
newHead = temp;
}
// now newHead is pointing to the actual new head
// temp (which is not accessable here) is same as nextGroup
// last step, reconnect everything and call recursion method
head.next = reverseKGroup(nextGroup, k);
return tail;
}
}