Java solution for merging O(m+n) time


  • 0
    A

    It is like merge part of merge sort.

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    		ListNode head = null;
    		ListNode n = null;
    		ListNode prev = null;
    		while (l1 != null && l2 != null) {
    
    			if (l1.val < l2.val) {
    				n = l1;
    				l1 = l1.next;
    			} else {
    				n = l2;
    				l2 = l2.next;
    			}
    			if (head == null)
    				head = n;
    			if (prev != null)
    				prev.next = n;
    			prev = n;
    
    		}
    		if (l1 != null) {
    			if (prev == null) {
    				return l1;
    			} else
    				prev.next = l1;
    		}
    		if (l2 != null) {
    			if (prev == null)
    				return l2;
    			else
    				prev.next = l2;
    		}
    
    		return head;
    	}
    

Log in to reply
 

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