Only one pass java solution (no counting), O(1) space. with some explanations


  • 0
    D

    The main trick is to re-reverse end of list if list's size is not a multiple of k.

    public ListNode reverseKGroup(ListNode head, int k) {
            if(k <= 1 || head == null){
                return head;
            }
            
            ListNode dummy =  new ListNode(0);
            dummy.next = head;
            
            ListNode pre = dummy;
            ListNode tail = head;
            k--;//reversing k nodes, need k-1 repeated operations.
            while(tail != null){
                ListNode then = tail.next;
                int count = k;
                //We reverse current kGroup
                while(count != 0 && then != null){
                    count--;
                    tail.next = then.next;
                    then.next = pre.next;
                    pre.next =then;
                    then = tail.next;
                }
                if(count == 0){//Reached end of kGroup. we reinit for next group.
                    pre = tail;
                    tail = then;
                    count = k -1;
                    continue;
                }
                //premature end of group, we have to re-reverse
                tail = pre.next;
                then = tail.next;
                while(then != null){
                    tail.next = then.next;
                    then.next = pre.next;
                    pre.next =then;
                    then = tail.next;
                }
                tail = then;
    
            }
            return dummy.next;
        }

Log in to reply
 

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