Short but recursive Java code with comments


  • 154
    S

    Hi, guys!
    Despite the fact that the approach is recursive, the code is less than 20 lines. :)

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode curr = head;
        int count = 0;
        while (curr != null && count != k) { // find the k+1 node
            curr = curr.next;
            count++;
        }
        if (count == k) { // if k+1 node is found
            curr = reverseKGroup(curr, k); // reverse list with k+1 node as head
            // head - head-pointer to direct part, 
            // curr - head-pointer to reversed part;
            while (count-- > 0) { // reverse current k-group: 
                ListNode tmp = head.next; // tmp - next head in direct part
                head.next = curr; // preappending "direct" head to the reversed list 
                curr = head; // move head of reversed part to a new node
                head = tmp; // move "direct" head to the next node in direct part
            }
            head = curr;
        }
        return head;
    }
    

    Hope it helps!


  • 0
    W

    Very concise solution. Thank you for sharing!


  • 2
    M

    Although it may not meet the requirement of the question that that it should use constant memory, the code is really nice and concise.


  • 2
    S

    sweet code and it's easy to understand. Thanks!


  • -5
    S

    Actually, there is a way to write recursive in O(1) space. Just put reverseKGroup(curr, k); at the end.


  • 8
    Y

    I don't quite understand. How can a recursive function only use O(1) space? In my opinion, a recursive function must occupy at least O(n) stack space, where n is the depth of the recursion.


  • 0
    S

    Consider this structure

    recursive(x){
        if(x<1)
            return 0
        else
            recursive(x-1)
    }

  • 1
    D

    Could you please give more detail on the space complexity? I think even the function is void type, we still need O(k) space on stack for storing the parameters in each recursion.


  • 1
    S

    You are right. I found out that the stack is always needed. There must be O(k) space required.


  • 0
    K

    this is so elegant..


  • 0
    C

    so beautiful...


  • 0
    M

    what you said is the tail call recursion. I think java can optimize tail call recursion to O(1). since it will be nothing more than a while loop. But, it will become a totally different solution, not just put the recursive call to the end


  • 1
    D

    It's simply WRONG if put reverseKGroup(curr, k); at the end.


  • 0
    J

    this is cray..


  • 3
    J

    The problem only allowed O(1) memory,
    while your solution uses O(N) space.


  • 0
    D

    Great solution. Really easy to understand with comments.


  • 0
    C

    this is beautiful, easy to understand


  • 29
    O

    Check this out. 16 Lines Non-recursive.

    public ListNode reverseKGroup(ListNode head, int k) {
            int n = 0;
            for (ListNode i = head; i != null; n++, i = i.next);
            
            ListNode dmy = new ListNode(0);
            dmy.next = head;
            for(ListNode prev = dmy, tail = head; n >= k; n -= k) {
                for (int i = 1; i < k; i++) {
                    ListNode next = tail.next.next;
                    tail.next.next = prev.next;
                    prev.next = tail.next;
                    tail.next = next;
                }
                
                prev = tail;
                tail = tail.next;
            }
            return dmy.next;
        }

  • 0
    N

    What would be the time complexity ?


  • 0
    N

    What would be Time Complexity ?


Log in to reply
 

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