[LeetCode 25] Reverse Nodes in k-Groups

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.

``````/**
* 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) {
}
for (int i = 0; i < k; i++) {
if (nextGroup == null) {
// there isn't k nodes in this list
}
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 tail = null;
for (int i = 0; i < k; i++) {