Question

Formatted question description: https://leetcode.ca/all/25.html

25	Reverse Nodes in k-Group

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

Algorithm

In fact, the original linked list is divided into several small segments, and then they are flipped separately. Then there must be a total of two functions, one for segmentation and one for flipping. Take the example given in the title, for Given a linked list 1->2->3->4->5, generally when dealing with linked list problems, most of the time, a dummy node will be added at the beginning, because the head node may change when the linked list is flipped, in order to record the current latest, The dummy node introduced by the position of the head node of the dummy node, the linked list after adding the dummy node becomes -1->1->2->3->4->5. If k is 3, the goal is to change 1,2 ,3 If you flip it, you need some pointers. Pre and next point to the front and back positions of the linked list to be flipped. After flipping, the position of pre is updated to the following new position

prev is dummy, then current is always node ‘1’, ‘1’ will move each iteration of while loop for k-group swap

prev is static during the full while loop of while (kcopy > 0) // 1->2->3->4->5 , k=3 // 2,1,3,4,5 // 3,2,1,4,5 // => always getting 1’s next for prev’s next => current (below) not changing in one-batch-swap

Code

Java

public class Reverse_Nodes_in_k_Group {

    class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            ListNode dummy = new ListNode(0);
            dummy.next = head;

            ListNode prev = dummy;

            // count total nodes
            ListNode tmp = head;
            int count = 0;
            while (tmp != null) {
                count++;
                tmp = tmp.next;
            }

            // 1->2->3->4->5 , k=3
            // 2,1,3,4,5
            // 3,2,1,4,5
            // => always getting 1's next for prev's next => current (below) not changing in one-batch-swap

            // if only one node left, then no swap
            while (count >= k) {

                ListNode originalFirst = prev.next;

                int kcopy = k - 1; // @note: since current node is already counted as 1
                while (kcopy > 0) { // both prev and current, not changed in while loop

                    ListNode nextNextCopy = originalFirst.next.next;
                    ListNode firstInGroup = prev.next;

                    prev.next = originalFirst.next;
                    prev.next.next = firstInGroup;
                    originalFirst.next = nextNextCopy;

                    kcopy--;
                }

                // @note: update previous AND current. I forgot current...
                prev = originalFirst; // now current is the last one of this group
                count -= k;
            }

            return dummy.next;
        }
    }
}

All Problems

All Solutions