[LeetCode21]Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Analysis:

The idea is simple. Two point scan from the begin to end for two lists.

every time compare the value of the listnode, if n1.val< n2.val  newhead.next = n2  else newhead.next = n1.

java

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        ListNode temp = new ListNode(0);
        ListNode prev = temp;
        while(l1!=null && l2!=null){
        	if(l1.val>l2.val){
        		prev.next = l2;
        		l2 = l2.next;
        	}
        	else{
        		prev.next = l1;
        		l1 = l1.next;
        	}
        	prev = prev.next;
        }
        if(l1!=null) 
        	prev.next = l1;
        else if(l2!=null)
        	prev.next = l2;
        return temp.next;
    }

ListNode *merge2Lists(ListNode *head1, ListNode *head2){
        ListNode *head = new ListNode(INT_MIN);
        ListNode *pre = head;
        while(head1 != NULL && head2 != NULL){
            if(head1->val <= head2->val){
                pre->next = head1;
                head1 = head1->next;
            }else{
                pre->next = head2;
                head2 = head2->next;
            }
            pre = pre->next;
        }
        if(head1 != NULL){
            pre->next = head1;
        }
        if(head2 != NULL){
            pre->next = head2;
        }
        pre = head->next;
        delete head;
        return pre;
    }