Merge_two_sorted_list

/*
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.
*/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
      if (!l1) return l2;
      if (!l2) return l1;
      ListNode *dummyHead=new ListNode(INT_MIN);
      ListNode *p=dummyHead;//p is used to track down the new list.
      while(l1&&l2)
      {
        if (l1->val<=l2->val)
	{
	  p->next=l1;
	  p=p->next;
	  l1=l1->next;
	}
	else
	{
	  p->next=l2;
	  p=p->next;
	  l2=l2->next;
	}
      }  
      if (!l1) p->next=l2;
      if (!l2) p->next=l1;
      return dummyHead->next;  
    }
};

REMARK:
1 EASY. IDEA: Use a dummyHead to denote the first node in the new list and return dummyHead->next.It is not the only way though. Then use 2 pointers to walk though the 2 lists. done.
2. Time: O(n1+n2) where n1 and n2 are the length of the 2 lists repectively.