Leetcode 25 Reverse Nodes in k-Group

Leetcode 25 Reverse Nodes in k-Group

Edit Reverse Nodes in k-Group on GitHub

The problem description is as follow:

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

This problem seems difficult, but it will be much easier if we split the problem into small pieces.

Reverse A Single Linked List

Let’s take a look at the following singly linked list, we are trying to reverse nodes between ListNode Pre to ListNode End.

Since we are trying to reverse linked list between ListNode Pre to ListNode End, ListNode Last = Pre.next will always be the last node of the reversed linked list.

public ListNode reverse(ListNode pre, ListNode end){
       
       ListNode last=pre.next;
       ListNode cur=last.next;
       
       while (cur!=end){
           
           last.next=cur.next;
           cur.next=pre.next;
           pre.next=cur;
           
           cur=last.next;
       }
       return last;
   }

The code above is trying to reverse linked list between Pre and Cur, and we could then reverse the whole linked list by moving Cur to Cur.next.

Reverse Nodes in k-Group

After previous analysis, this problem is simple. For a singly linked list, we create a Dummy ListNode and point to it’s head. Then we use previous algorithm to reverse nodes in k-group:

/**
    * Reverse a link list between pre and next exclusively
    * a linked list:
    * 0->1->2->3->4->5->6
    * |           |   
    * pre        next
    * after call pre = reverse(pre, next)
    * 
    * 0->3->2->1->4->5->6
    *          |  |
    *          pre next
    */

public ListNode reverseKGroup(ListNode head, int k) {
        if (head ==null || k==1){
            return head;
        }
        
        ListNode dummy =new ListNode (0);
        dummy.next=head;
        
        ListNode pre=dummy;
        ListNode cur=head;
        
        int i=0;
        while (cur!=null){
            i++;   
            if (i%k==0){
                pre=reverse(pre,cur.next);
                cur=pre.next;
            }
            else {
                cur=cur.next;
            }
        }
        return dummy.next;
}

Since we are traversing the singly linked list at most twice, the time complexity is O(n).