遍历解法 | #合并两个排序的链表#

/*
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) return pHead2;
		if (!pHead2) return pHead1;
        // 把 list1 插入到 list2 中
		ListNode* i = new ListNode(0);
		ListNode* h = i; // 新头节点
		i->next = pHead1;
		ListNode* temp;
		while (pHead2 && i->next){
		  	// 找到下一个插入点
			while (i->next && pHead2->val > i->next->val) {
				i = i->next;
			}
			if (!i->next) break;
			// 把list2的当前节点插入到该位置
			temp = pHead2->next;
			pHead2->next = i->next;
			i->next = pHead2;
		  	// 新的i和pHead2
			pHead2 = temp;
			i = i->next;
		}
		if (!i->next) i->next = pHead2;
		return h->next;
    }
};