Straight forward 1ms Java O(n) Solution without extra space, but with comments ;-)


  • 0
    O
     /**
         * Since the original linked list will be divided into n/k portions which need to be reversed
         * plus the left over portion which does not need to be reversed
         * So basically my idea is to find those reversion needed portions and reverse them sequentially
         * then link them all and return the modified list at last
         */
        public static ListNode reverseKGroup(ListNode head, int k) {
            if(head == null || head.next == null || k == 1){ //handle edge cases
                return head;
            }
    
            int index = 1;
            ListNode pointer = head;
            ListNode previousPortionTail = head; //after each reversion, head of each portion will become the tail of each portion
    
            while(index <= k && pointer != null){ //find the first portion
                pointer = pointer.next;
                index++;
            }
    
            if(pointer == null && index <=k) // if k is bigger than the list size, just return origin list
                return head;
    
            ListNode nextStart = pointer;
            ListNode toReturn = advancedReverseList(head,nextStart); //reverse first portion of the original list, the boundary of it will be nothing but the next portion's start node
    
    
            while(pointer != null){ //keep looping the list
                if(index % k == 0){ //reverse the following portion of the original list
                    ListNode boundary = pointer.next;
                    previousPortionTail.next = advancedReverseList(nextStart,boundary); //link with the previous portion
                    previousPortionTail = nextStart; // update the tail of the previous portion
                    nextStart = boundary; //set the start node of the next portion
                    pointer = nextStart;
                }else{
                    pointer = pointer.next;
                }
                index++;
            }
            return toReturn;
        }
    
        /**
         * similar to ordinary reverse linked list method, but additionally check if node reaches the boundary node
         * and append boundary node to the end of the reversed linked list.
         */
        public static ListNode advancedReverseList(ListNode head, ListNode boundary) {
            if(boundary != null) {
                if (head == null || head.next == null || head.next == boundary) {
                    return head;
                }
            }else{
                if(head == null || head.next == null ){
                    return head;
                }
            }
            ListNode second = head.next;
            head.next = null;
            ListNode toReturn = advancedReverseList(second,boundary);
            second.next = head;
            head.next = boundary;
            return toReturn;
        }
    

Log in to reply
 

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