力扣21. 合并兩個有序連結清單（連結清單，疊代）

力扣21. 合并兩個有序連結清單（連結清單，疊代）

https://leetcode-cn.com/problems/merge-two-sorted-lists/

将兩個升序連結清單合并為一個新的升序連結清單并傳回。新連結清單是通過拼接給定的兩個連結清單的所有節點組成的。 

示例：

輸入：1->2->4, 1->3->4

輸出：1->1->2->3->4->4

方法 ：疊代

有點像歸排中合并的算法

動畫：

https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode/

想法：

我們可以用疊代的方法來實作上述算法。我們假設 l1 元素嚴格比 l2元素少，我們可以将 l2 中的元素逐一插入 l1 中正确的位置。

算法：

首先，我們設定一個哨兵節點 "prehead" ，這可以在最後讓我們比較容易地傳回合并後的連結清單。我們維護一個 prev 指針，我們需要做的是調整它的 next 指針。然後，我們重複以下過程，直到 l1 或者 l2 指向了 null ：如果 l1 目前位置的值小于等于 l2 ，我們就把 l1 的值接在 prev 節點的後面同時将 l1 指針往後移一個。否則，我們對 l2 做同樣的操作。不管我們将哪一個元素接在了後面，我們都把 prev 向後移一個元素。

在循環終止的時候， l1 和 l2 至多有一個是非空的。由于輸入的兩個連結清單都是有序的，是以不管哪個連結清單是非空的，它包含的所有元素都比前面已經合并連結清單中的所有元素都要大。這意味着我們隻需要簡單地将非空連結清單接在合并連結清單的後面，并傳回合并連結清單。

時間複雜度：O(n+m)。 因為每次調用遞歸都會去掉 l1 或者 l2 的頭元素（直到至少有一個連結清單為空），函數 mergeTwoList 中隻會周遊每個元素一次。是以，時間複雜度與合并後的連結清單長度為線性關系。

空間複雜度：O(1) 。疊代的過程隻會産生幾個指針，是以它所需要的空間是常數級别的。

#include "stdafx.h"

struct ListNode 
{
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
};

class Solution 
{
public:
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
	{
		ListNode* head = new ListNode(0);
		ListNode* cur = head;
		while (l1!=NULL && l2 != NULL)
		{
			if ((l1->val)<=(l2->val))
			{
				cur->next = l1;
				cur = cur->next;
				l1 = l1->next;
			}
			else
			{
				cur->next = l2;
				cur = cur->next;
				l2 = l2->next;
			}
		}
		while (l1 != NULL)
		{
			cur->next = l1;
			cur = cur->next;
			l1 = l1->next;
		}
		while (l2 != NULL)
		{
			cur->next = l2;
			cur = cur->next;
			l2 = l2->next;
		}
		return head->next;
	}
};

int main()
{
	Solution s;
	ListNode l1[3] = { 1,2,4 };
	l1[0].next = &l1[1]; l1[1].next = &l1[2];
	ListNode l2[3] = { 1,3,4 };
	l2[0].next = &l2[1]; l2[1].next = &l2[2];
	auto result = s.mergeTwoLists(l1, l2);
    return 0;
}