O(1) Space: Very intuitive easy to understand Java solution


  • 0
    M

    If you breakdown this problem in multiple pieces it is very easy.
    What if someone provides you a function that returns back three pieces of information for each K chunks of list.

    1. New head of the k chunk of link list
    2. Tail of k chunk of link list
    3. The immediate node that comes after this chunk.
      Example:
      1->2->3->4 and k = 3
      the function provides below and transforms link list to 3->2->1
      newHead = 3
      newTail = 1
      nextToDealNode = 4

    Now all you need to do is point the newTail with the nextToDealNode.
    When there is no more nextToDealNode, you are down.

    Writing such function is not that difficult task.

    public class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            if(k <= 1 || head==null){return head;}
            
            Result r = reverseKList(head,k);
            ListNode nHead = r.head;
            ListNode nTail = r.tail;
            
            while(r.nextToDeal != null){
                r = reverseKList(r.nextToDeal, k);
                nTail.next = r.head;
                nTail = r.tail;
            }
            
            return nHead;
        }
        
        
        private Result reverseKList(ListNode head, int k){
            boolean okToRev = canReverse(head, k);
            if(! okToRev){
                return new Result(head, null, null);
            }
            
            ListNode nTail = head; // preserve tail
            ListNode n = head, temp = null, prev = null;
            while(k > 0){
                temp = n.next;
                if(prev !=null){
                   n.next = prev;
                }            
                prev = n;
                n = temp;
                k--;
            }
            
            // New head is prev
            // Next to deal with node is temp
            // Tail is old head
            nTail.next = null;
            return new Result(prev,nTail,temp);
        }
        
        /*
            true: If the list is big enough for k
        */
        private boolean canReverse(ListNode head, int k){
            while(k > 0 && head !=null){
                k--;
                head = head.next;
            }
            
            // If we hit tail, we will not reverse the list
            return (head == null && k!=0) ? false : true;
            
        }
        
        private static class Result{
            ListNode head, tail, nextToDeal;
            public Result(ListNode head, ListNode tail, ListNode nextToDeal){
                this.head = head;
                this.tail = tail;
                this.nextToDeal = nextToDeal;
            }
        }
    }
    

Log in to reply
 

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