Ac solution code


  • 0

    Solution1. Non-Recursive Solution - Special thanks for StefanPochmann's comment

      Assuming we have a linkedList: A..B..C..D:
    
      Say A..B is a k-Group,	   
      
      We need 3 steps to reverse the k-Group: 
      1) Find the kth node B (tail)
      2) B..A  C..D: reverse A..B to B..A
      3) B..A..C..D: connect the new tail A with the next head C
    
      Keep the above steps, util it reaches the end of the linkedList.
    

    JAVA Code:

    public ListNode reverseOneGroup(ListNode head, ListNode nextHead) {// Reverse one k-group
    	ListNode prev = null;
    	while (head != nextHead) {
    		ListNode tmp = head.next;    		
    		head.next = prev;
    		prev = head;    		
    		head = tmp;
    	}
    	return prev;    		
    } 
    
    public ListNode reverseKGroup(ListNode head, int k) {        
            ListNode dummyHead = new ListNode(0); 
            ListNode lastTail = dummyHead;
            ListNode cur = head;
            
    	    dummyHead.next = head;
            while (cur != null) {
                int count = 0;
    	        while (cur != null && count < k-1) {// Find the tail of the current k-group
    	            count++;
    	            cur = cur.next;
    	        }  
    	        if (cur == null) break;// Reached the end: the remaining nodes are less than k
    	        
    	        cur = cur.next;// Next head
    	        lastTail.next = reverseOneGroup(head, cur);// lastTail: connect with the new head after reversal
    	        head.next = cur;// curTail: connect with the next head. (head is reversed to the current tail)
    	        lastTail = head;
    	        head = cur;// Set head with the next head
            }                
            return dummyHead.next;
    }
    

    Solution2. Recursive Solution - Special thanks to @shpolsky

    As only constant memory is allowed, recursive solution actually doesn't satisfy the requirement, because it needs system stack space for recursion.

    1) Find kth node (Next head after k-group)
    2) Reverser k..end-1 as the next node of 0..k-1(k-group)
    3) Reverse 0..k-1(k-group)
    4) Keep the above steps recursively
    

    Time Complexity: O(n)

    1) For each k-Group, we need O(k)(Find kth node) + O(k)(Reverse k nodes)=O(2k)=O(k)
    2) There're (n / k) groups totally  
    So the total time complexity = O(k) * (n / k) = O(k * (n / k)) = O(n).
    

    JAVA Code:

    public ListNode reverseKGroup(ListNode head, int k) {
    	ListNode nextHead = head;
    	for (int i = 0; i < k; i++) { //Find the next head after k-group (kth node, because k-group is 0..k-1)
    	    if (nextHead == null) return head;// less than k nodes left, return the orginal head
    		nextHead = nextHead.next;
    	}
    	
    	ListNode previousTail = head;// head of (0..k-1)group becomes the previous tail of (k..n)group
    	
    	// reverse 0..k-1
    	ListNode prev = null;
        for (int i = 0; i < k; i++) {
    		ListNode next = head.next;
    		head.next = prev;// point head.next back to previous
    		prev = head;// update current 'prev'
    		head = next;// forward head						
    	}
    	
    	
    	// Append result of (k..n) nodes to (0..k-1) group
    	previousTail.next = reverseKGroup(nextHead, k);
    
    	return prev;
    }
    

  • 0

    "Only constant memory is allowed."


  • 0

    Haha, didn't notice that, gonna modify it to non-recursive ;) Thanks, buddy!


Log in to reply
 

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