Leetcode — 25. Reverse Nodes in k-Group

The link to the problem: https://leetcode.com/problems/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.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

For example, 1->2->3->4->5, k=2 
output: 2->1->4->3->5

The difficulty of this problem is HARD. It is highly recommended to know how to solve 92. Reverse Linked List II or read this story to know the idea of how to reverse a linked list partially.

* my solution below will use the idea in the story I mentioned previously.

For me, the most challenging thing in this type of question is how we correctly get the node we want.

Coding Logic:

I think this question is a transformation of Leetcode 92. In Leetcode 92, the input is a linked list, and two integer variables m and n. In this problem, it seems like we need to keep partially reversing the list until we cannot find m and n.
For example, if the total length of the linked list is 7 and k is 3, we need to reverse twice, the first time m=1 and n=3; and the other time is m=4 and n=6.

Since this is a linked list problem, we cannot know the length of the linked list without actually traverse the whole list. That is to say, we cannot directly reverse the list without being sure we are allowed to. (Suppose the length of the linked list is n, it is possible that n<k or n%k is not 0)

However, what we at least know for sure is when are we going to start to reverse the list. ( we will use revHead to store the starting node of the reverse this time)

Then we will use a counter to count the number of nodes from revHead to know when we should start to reverse and where this reverse ends. (i.e., once the counter reaches k)

* There are a lot of different variable names for the node in the code —

* dummy - a dummy node which points to head by default. It is designed to point to the head of the result linked list.
* node - we use node to traverse the whole linked list, like an iterator. if node=null, then it means we are done traversing the list.
* revHead - the starting node of this reverse
* preRevHead - the previous node of this reverse(not included in the reverse)
* Xnode - the ending node of this reverse
* Ynode - the node right after reverse(not included in the reverse)
Hence, before we start the reverse, the list looks like:
... -> preRevHead -> revHead -> ... ->Xnode -> Ynode -> ...
After reverse, we expected the list looks like: 
... -> preRevHead -> Xnode -> ... -> revHead -> Ynode -> ...

Below is my 0ms code that beats 100%:

public ListNode reverseKGroup(ListNode head, int k) {
        if(head==null || head.next==null || k==1 )
            return head;
        ListNode dummy = new ListNode(0,head);
        int count = 1;
        ListNode node = head;
        
        ListNode preRevHead = dummy;
        ListNode revHead = node; 
        while(node!=null)
        {
            if(count<k) 
            {
                count++;
                node = node.next;
                continue;
            }
            //when count ==k, we start to reverse! 
            ListNode xNode = node;
            ListNode yNode = node.next;
            //start to do reverse from revHead to xNode
            ListNode pre = null;
            ListNode cur = revHead;
            for(int i=0;i<k;i++)
            {
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            //now pre is the new head of reversed list
            preRevHead.next = pre;
            revHead.next = yNode;
            //update preRevHead and revHead
            preRevHead = revHead;
            revHead = yNode;
            
            //node be the next node and continue traversing the list
            node = yNode;
            count = 1;
        }
        
        
        return dummy.next;
    }

Time Complexity: O(n)
Space Complexity: O(1) ✌️