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

递归法：

/*
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 || !pHead2) return pHead1 ? pHead1 : pHead2;
		if(pHead1->val < pHead2->val) {
			pHead1->next = Merge(pHead1->next, pHead2);
			return pHead1;
		} else {
			pHead2->next = Merge(pHead1, pHead2->next);
			return pHead2;
		}
    }
};

头节点双链表法：

/*
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 || !pHead2) return pHead1 ? pHead1 : pHead2;
		ListNode *ret = new ListNode(-1);
		ListNode *cur = ret;
		while(pHead1 && pHead2) {
			ListNode* tmp = pHead1->val < pHead2->val ? pHead1 : pHead2;
			cur->next = tmp;
			if(tmp == pHead1) pHead1 = pHead1->next;
			else pHead2 = pHead2->next;

			cur = cur->next;
		}
		cur->next = pHead1 ? pHead1 : pHead2;

		return ret->next;
    }
};