試解leetcode算法題--合并兩個有序連結清單

<題目表述>

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

示例：

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

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

<原題連結>

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

<思路>

這裡連結清單合并可以直接在原連結清單上修改即可，我們設三個變量*p, *q, *r以及存放最終結果的表頭 *ans，其中p初始指向較小的第一個元素所在的連結清單，q指向另一個連結清單，r為遊标，周遊兩個連結清單。

當p處的值>=q處的值時，r指向q所在的連結清單，反之r指向p所在的連結清單。

當l1、l2其中一個連結清單周遊完成後，如果另外一個連結清單還有元素，那麼将其直接接到r指針後面即可。

<樣例代碼>

#include<iostream>
using namespace std;

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

class Solution {
public:
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
		ListNode *p, *q, *r, *ans;
		if (l1 == NULL)		//注意這裡，判斷是否為空
			return l2;
		if (l2 == NULL)
			return l1;
		p = l1->val <= l2->val ? l1 : l2;		//注意這裡，将p設為開始較小的那個連結清單頭。
		q = l1->val <= l2->val ? l2 : l1;
		ans = p; r = p; p = p->next;
		
		while (p != nullptr && q != nullptr)
		{
			if (q->val <= p->val)
			{
				r->next = q;
				r = q;	//r指向q所在的連結清單
				q = q->next;
			}
			else
			{
				r->next = p;
				r = p;	//r指向p所在的連結清單
				p = p->next;
			}
		}
		if (p != nullptr)
			r->next = p;
		if (q != nullptr)
			r->next = q;
		return ans;
	}
};