[LeedCode OJ]#21 Merge Two Sorted Lists

[LeedCode OJ]#21 Merge Two Sorted 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)
		{
			ListNode *l3 = new ListNode(0);
			ListNode *newlist = l3;
			while(l1&&l2)
			{
				if(l1->val<=l2->val)
				{
					l3->next = l1;
					l1 = l1->next;
				}
				else
				{
					l3->next = l2;
					l2 = l2->next;
				}
				l3 = l3->next;
			}
			l3->next = l1?l1:l2;
			return newlist->next;
		}
};