Java Compare Recursive and Iterative Solution


  • 0
    X

    Recursive
    Recursion is a more straightforward way of this problem. Reverse the first k nodes, and leave the rest of the list to the recursion.

    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null) return null;
        ListNode node = head;
        for(int i = 1; i <= k; i++) {
            if(node == null) return head;
            node = node.next;
        }
        ListNode cur = head, nextHead = reverseKGroup(node, k);
        while(cur != node) {
            ListNode tmp = cur.next;
            cur.next = nextHead;
            nextHead = cur;
            cur = tmp;
        }
        return nextHead;
    }
    

    Iterative
    Recursive method is actually using more than constant space. The recursion depth is (n / k), which is also the space complexity. Use iterative method to get the real constant space implementation.

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        while(head != null){
            ListNode node = head;
            for(int i = 1; i <= k; i++) {
                if(node == null) {
                    prev.next = head;
                    return dummy.next;
                }
                node = node.next;
            }
            ListNode cur = head, nextHead = node;
            while(cur != node) {
                ListNode tmp = cur.next;
                cur.next = nextHead;
                nextHead = cur;
                cur = tmp;
            }
            prev.next = nextHead;
            prev = head;
            head = node;
        }
        return dummy.next;
    }
    

Log in to reply
 

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