题解 | #合并两个排序的链表#

（递归解题思路来自剑指offer，思路真的巧妙，以前自己做的都是迭代，边界条件需要注意的多一点）

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if (pHead1 == nullptr) return pHead2;
        if (pHead2 == nullptr) return pHead1;
		ListNode* pRes = nullptr;
		if (pHead1->val < pHead2->val) {
			pRes = pHead1;
			pRes->next = Merge(pHead1->next, pHead2);
		}
		else {
			pRes = pHead2;
			pRes->next = Merge(pHead1, pHead2->next);
		}
		return pRes;
	}
};

迭代解法

class Solution {
  public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if (pHead1 == NULL)    return pHead2;
        if (pHead2 == NULL)    return pHead1;
        ListNode* p1 = pHead1;
        ListNode* p2 = pHead2;
        ListNode* res = p1->val > p2->val ? pHead2 : pHead1;
        ListNode* p3 = res;
        if (res == pHead1) {
            p1 = p1->next;
        }
        if (res == pHead2) {
            p2 = p2->next;
        }
        while (p1 && p2) {
            if (p1->val <= p2->val) {
                p3->next = p1;
                p3 = p1;
                p1 = p1->next;
            } else if (p1->val > p2->val) {
                p3->next = p2;
                p3 = p2;
                p2 = p2->next;
            }
        }
        p3->next = p1 ? p1 : p2;
        return res;
    }
};