Simple Java iterative solution with explanation


  • 4
    D

    The basic idea is for each step,we set the the node after head as the list's new head, so that head then is tail. After reversing k nodes, we update the references and iterate through the whole list. If the size of the list is a multiple of k, the list is safely returned. Otherwise, a recursive call is made on the left-out nodes to undo the reverse. So the whole iteration times will be (n + n%k)

    Here is an example of how it works(case of K = 3):

    Initial:

    sentinel -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 ->...
        |       |    |
      dummy    tail newHead   
    

    Set the node after tail @newHead as the new head. And the list:

    sentinel -> 2 -> 1 -> 3 -> 4 -> 5 -> 6 ->...
        |            |    |
      dummy        tail newHead
    

    Set node after tail as new Head:

     sentinel -> 3 -> 2 -> 1 -> 4 -> 5 -> 6 ->...
        |                  |
      dummy               tail   
    

    3 nodes are reversed. Update the references:

    sentinel -> 3 -> 2 -> 1 -> 4 -> 5 -> 6 ->...
                          |    |    |
                        dummy tail newHead   
    

    Here is code:

    public ListNode reverseKGroup(ListNode head, int k) {
        if (k < 2 || head == null) return head;
        ListNode sentinel = new ListNode(0);
        sentinel.next = head;
        ListNode dummy = sentinel, tail = head, newHead;
        While (true) {
            int count = k - 1;
            while (count > 0) {
                if (tail.next != null) {
                    newHead = tail.next;
                    tail.next = newHead.next;
                    newHead.next = dummy.next;
                    dummy.next = newHead;
                    count--;
                } else { 
                    /// list size is not multiple of k, a recursive call on the left-out nodes to undo the reverse
                    dummy.next = reverseKGroup(dummy.next, k - count);
                    return sentinel.next;
                }
            }
            if (tail.next == null) return sentinel.next; /// list size is multiple of k, safely return
            dummy = tail;
            tail = tail.next;
        }
    }

  • 1
    S

    Very nice solution. But can you explain how the complexity is O(n + n%k); Also can you tell what is the complexity of my code.

    Thank you.

     public static ListNode reverseKGroup(ListNode head, int k) {
    		if(head == null || head.next == null || k <=1){
    			return head;
    		} 
    		ListNode slow = null, newHead = new ListNode(-1), pre = newHead, temp = null, cur = head;
    
    		while(cur != null) {
    			int i = 0;
    			temp = cur;
    			for(i = 0; cur != null && i < k; ++i) {
    				slow = cur;
    				cur = cur.next;
    			}
    			slow.next = null;
    
    			if(i < k) {
    				pre.next = temp;
    			}
    			else {
    				pre.next = reverseList(temp);
    				i = 0;
    				while(pre != null && i < k) {
    					pre = pre.next;
    					i++;
    				}
    			}
    		}
    		return newHead.next;
    	}
    
    	public static ListNode reverseList(ListNode head) {
    		ListNode reverse = null;
    		ListNode next = null;
    		while(head != null) {
    			next = head.next;
    			head.next = reverse;
    			reverse = head;
    			head = next;
    		}
    		return reverse;
    	}
    

  • 0
    D

    Basically, my idea is to walk through the listnodes, while at the same time, reverse the nodes and keep counting the nodes reversed. Start the next round after reversing k nodes Group. When the number of the nodes n is a multiply of k, after N iteration, the list is k reversed. But when N is not a multiply of k, let's say to reverse 1 -> 2 -> 3 -> 4 -> 5 in 3 Group, after N iteration the list becomes 3 -> 2 -> 1 -> 5 -> 4. But the question requires "left-out nodes in the end should remain as it is". So a recursive call is made to undo the reverse of the left-out nodes. And there are n%k left-out nodes. So I said there will be (n + n%k) iterations.

    Your idea is to firstly locate k nodes Group then reverse them, iteratively. Both your and my solution visit the nodes a constant of times, so using the big O notation, i think the complexity of both solutions are O(n), (only with difference up to a constant factor).


  • 0
    J

    Thanks for sharing, really helpful.


Log in to reply
 

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