实现思路

在这里我使用的是开辟一个新链表，然后通过比较给定两个链表的值来插入到这个新链表中，最后返回新的链表、

代码实现

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
    	ListNode *res = new ListNode(-1);
    	ListNode *cur = res;
        while(pHead1&&pHead2)
        {
        	if(pHead1->val<=pHead2->val)
        	{
        		cur->next = pHead1;
        		pHead1 = pHead1->next;
        	}
        	else
        	{
        		cur->next = pHead2;
        		pHead2 = pHead2->next;
        	}
            cur = cur->next;
        }
        cur->next = pHead1?pHead1:pHead2;
        return res->next;
    }
};

小技巧：虚拟头结点
为了实现所有节点的统一，给第一个节点前也加了个前驱结点。这样在处理头结点的时候可以像处理其他节点一样。

    	ListNode *res = new ListNode(-1); //这个参数参考上述结点的结构体。
    	ListNode *cur = res;

上述两行代码就是创建了一个虚拟头结点（也可以说创建了一个新的链表），然后通过用cur间接操作 res不会丢失原指向 然后合并完返回了。

图解

我刚开始有一点疑问就是：为什么这个res指针能和其他两个链表连接起来？我之所以有这个疑问是因为我的思路混了，我一直想的是定义一个指针，保存链表开始的位置用于返回。其实这是第二种解题思路，就是把一个链表不断地插入到另一个链表中，这个过程需要保存链表头的位置。