3ms, 2 pass, const space, iterative Java solution, with explanation


  • 0
    A

    O(n) O(1)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            if(head==null || head.next==null) return head;
            int i,j,count=1,set;
            ListNode h=head,n,c=head,end=null;
            //Count elements in list
            while(c.next!=null){
                count++;
                c=c.next;
            }
            if(count<k) return head;
            //count no of 'sets' or sub-lists with k elements each.
            set = (count - count%k)/k;
            
            j=k-1; 
            /*  Reverse each set iteratively (without impacting the extra elements left at last, if any).
                For each set of size k, apply (k-1) reverse operations. 
                Ex) k=3 => A three element sub-list [1,2,3] 
                => 2 iterations to reverse that sub-list. [1,2,3] => [2,1,3] => [3,2,1]
            */
            while(set>0){
                c=h; // First/current node of this set.
                i=j; // No of reverse operations = k-1
                n=c.next; // node next to current node.
                
                while(i>0){
                    c.next = n.next;
                    n.next=h;
                    h=n;
                    n=c.next;
                    i--;
                }
                /*
                    If this is not the first set, join the 'end' of previous set to the head of this set.
                    If this is the first set, set the head of entire list as head of this set.
                */
                if (end!=null) end.next=h;
                else head=h;
                
                //modify values for next set.
                end=c; //points to last node of this reversed set.
                h=n;   // next set's head.
                set--;
            }
            return head;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.