Non-recursive Java solution and idea


  • 24
    Y

    Reference:
    http://www.cnblogs.com/lichen782/p/leetcode_Reverse_Nodes_in_kGroup.html

    First, build a function reverse() to reverse the ListNode between begin and end. See the explanation below:

       /**
         * Reverse a link list between begin and end exclusively
         * an example:
         * a linked list:
         * 0->1->2->3->4->5->6
         * |           |   
         * begin       end
         * after call begin = reverse(begin, end)
         * 
         * 0->3->2->1->4->5->6
         *          |  |
         *      begin end
         * @return the reversed list's 'begin' node, which is the precedence of node end
         */
    

    Then walk thru the linked list and apply reverse() iteratively. See the code below.

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode begin;
        if (head==null || head.next ==null || k==1)
        	return head;
        ListNode dummyhead = new ListNode(-1);
        dummyhead.next = head;
        begin = dummyhead;
        int i=0;
        while (head != null){
        	i++;
        	if (i%k == 0){
        		begin = reverse(begin, head.next);
        		head = begin.next;
        	} else {
        		head = head.next;
        	}
        }
        return dummyhead.next;
        
    }
    
    public ListNode reverse(ListNode begin, ListNode end){
    	ListNode curr = begin.next;
    	ListNode next, first;
    	ListNode prev = begin;
    	first = curr;
    	while (curr!=end){
    		next = curr.next;
    		curr.next = prev;
    		prev = curr;
    		curr = next;
    	}
    	begin.next = prev;
    	first.next = curr;
    	return first;
    }

  • 0
    C

    it's not the constant space


  • 0
    P

    why it's not the constant space?


  • 0
    S
    This post is deleted!

  • 0
    B

    It is constant space. No matter what the k is, you use the same number of ListNode references.


  • 0
    L

    beautiful solution


  • 0
    R

    Amazing Solution!! Specially the use of reverse. You have my upvote!


  • 0
    A

    Similar Idea:

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            // Save the previous reversed pointer in prev and in wach iteration use prev.next to set the previous ptr to the current reversed.
            ListNode tempNode = new ListNode(0);
            tempNode.next = head;
            ListNode tempHead = head;
            ListNode prev = tempNode;
            while(tempHead!=null){
                // Starting of each reversed list, it will become the last after reversing
                ListNode klast = tempHead;
                int num = k;
                // Jump k 
                while(num>0 && tempHead!=null){
                    tempHead = tempHead.next;
                    num--;
                }
                // If cannot reverse
                if(num!=0) {
                    prev.next = klast;
                    break;
                }
                // start of each reversed group
                ListNode kstart = reverse(klast,k);
                
                // Use previous's next to point to curr reversed
                prev.next = kstart;
                // Set prev to current rev end.
                prev = klast; 
            }
            return tempNode.next;
            
        }
        
        // Standard reverse code
        public ListNode reverse(ListNode head, int k){
            ListNode prev = null;
            while(head!=null && k>0){
                ListNode next = head.next;
                head.next = prev;
                prev = head;
                head = next;
                k--;
            }
            return prev;
        }
        
    }
    

Log in to reply
 

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