Clean Iterative Java In-place Solution


  • 0
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null)
            return l2;
        if(l2==null)
            return l1;
        
        ListNode root = l1.val>l2.val ? l2 : l1;
        // current represents this root list
        ListNode currentPre = root;
        ListNode current = root.next;
        // other represents other list than root list
        ListNode other = root==l1 ? l2 : l1;;
        
        while(current!=null) {
            if(current.val <= other.val) {
                current = current.next;
                currentPre = currentPre.next;
            } else {
                currentPre.next = other;
                other = current;
                current = currentPre.next;
                
                current = current.next;
                currentPre = currentPre.next;
            }
        }
        
        currentPre.next = other;
        
        return root;
    }

  • 0

    I just found another way of coding, inspired by merge k linked list, poll each smaller node of two list and build up the final list.

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null)
            return l2;
        if(l2==null)
            return l1;
        ListNode root = l1.val>l2.val ? l2 : l1;
        ListNode end = root;
        ListNode node1 = l1.val>l2.val ? l1 : root.next;
        ListNode node2 = l1.val>l2.val ? root.next : l2;
        while(node1!=null && node2!=null) {
            if(node1.val<=node2.val) {
                end.next = node1;
                end = node1;
                node1 = node1.next;
            } else {
                end.next = node2;
                end = node2;
                node2 = node2.next;
            }
        }
        end.next = node1==null ? node2 : node1;
        return root;
    }

Log in to reply
 

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