Java PURE bottom-up recursive solution without "while or for" loop


  • 0

    The idea is to add a dummy head to divide into segments of k nodes.
    First segment looks like D->1->2->3->...->k
    2nd segment looks like k->k+1->k+2->k+3->...->k+k
    ......
    The helper function returns null if the segment has less than k nodes.
    Or, returns the kth node as the new head node for the reversing order.
    Also, during bottom-up, we need to reverse the pointer if the return is not null.
    In order to do the reversal, a variable node is used to store the next node of the current node.

    public class Solution {
        ListNode helper(ListNode head, ListNode cur, int k, int idx) {
            ListNode node = null;
            if (cur==null) return null; // less than k nodes
            if (idx==0) { // end of one segment
                node = helper(cur, cur.next, k, k-1); // go to the next segment
                head.next.next = node == null? cur.next : node; // connect the head node to the next segment
                return cur; // return the kth node as the new head
            }
            node = cur.next; // store the next node
            ListNode ret = helper(head, node, k, idx-1); // find next node in this segment
            if (ret != null ) { // found a full k-node segment
                if (node != null) node.next = cur; // reverse the connection
                return ret; // return the new head node
            }
            return null; // found a segment less than k nodes
        }
        
        public ListNode reverseKGroup(ListNode head, int k) {
            if (k<=1 || head == null) return head;
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            ListNode ret = helper(dummy, head, k, k-1);
            return ret == null? head : ret;
        }
    }
    

Log in to reply
 

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