思路：

合并链表最基本的两个思路：
1.吧表头最小的一个抽出，然后比较被抽后的剩下的链表继续操作
2.比较表头链表然后选择最小的一个（抽出）插入到没被选中的链表的合适的位置（并不是表头的下一个，而是那种一边<=另一边>的中间点插入，这里思路混乱了废了一些时间）,这个版本繁琐远不如上个版本好，没有去实现。

然后1又有递归和非递归写法，非递归最熟就是遍历两个链表，递归的因为非递归太简洁直观而想不到怎么需要递归哪里递归，看了题解后别人其实就是吧非递归版本的迭代过程用递归实现而已。但其实这样也有个作用：
1.非递归的操作其实是取出每一个，然后有一个专门的头节点负责串起来（push_back），每一个操作其实是串下一个，所以第一个操作就麻烦了第一个由谁来串他，初始化为头节点本身也不能解决这个问题，于是直接引入个空的头节点就解决了，最后把空的头节点去掉即可。
2.递归版本如果也是按照上面的思路来如果也要个头节点串接则需要个贯穿整个递归的容器，但递归还有另一种稍微有一点区别的做法：每个轮次做的是选出最小的一个和返回，两步的中间是当前串接下一个最小的一个，于是没有了头节点的问题（和非递归每次做的事情是有点差别的），然后他的代码看起来也有点奇怪，像前序又像后续，其实是前序，每次的操作是找最小然后传入排除最小的剩下两个链表（会影响后续递归的操作在调用之前），只不过后来又多了一步对返回值扣上（不扣上也是返回自己函数照常运行，只不过链表断链，且返回值不是影响下个返回值的操作？，所以说算后续有点奇怪，当然也不排除可以前后续一起的）

然后在实际敲代码还发现了一个问题，那就是在表尾null，最小的应该算null于是null要赋值剩下的那个表，但null指针赋值是没用的，所以参数要传入引用，在指针引用这一块又花了时间回顾了下。最后还发现返回值不用引用，引用是为了在函数内的操作生效，返回值扣上的是值，返回引用反而不知道有没有事情？然后又细想了一下，发现返回引用也没事，因为我在里面把表尾对象的next（null）的引用在遍历到null这个环节时给他扣上下个链表，然后返回对方（返回引或非引用用时在null赋值后返回自己都没错的，在外面又赋值了一遍如果是引用，则是上个引用的值赋值为返回的自己的值即下个链表的值<这里混了引用的绑定和赋值，这里不会是绑定>，若返回的是对方也没错同理），然后在外面又是next扣上返回的下个链表，是重复的操作，到这里才发现，即使到了null也不用在里面处理扣下个链表，每个轮次只负责返回最小的，扣链表是这个轮次之外做的事情。

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};
//11:44--12:04非递归
class Solution2 {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(pHead1 == NULL)
            return pHead2;
        if(pHead2 == NULL)
            return pHead1;
        ListNode* head=new ListNode(-1), *p = head;

        while(pHead1 && pHead2){
            if(pHead1->val <= pHead2->val){
                p->next = pHead1;
                pHead1 = pHead1->next;
            }else{
                p->next = pHead2;
                pHead2 = pHead2->next;
            }
            p = p->next;
        }
        if(pHead1){
            p->next=pHead1;
        }else{
            p->next=pHead2;
        }
        return head->next;
    }
};
//12:11--12:49--13:28 递归1思路混乱版
class Solution {
public:
    ListNode* Merge(ListNode* &pHead1, ListNode* &pHead2)  //这里的引用是为了该值，但其实是不必要的
    {
        if(pHead1 == NULL){
            pHead1 = pHead2;//不管是返回引用非引用，这里返回自己或对方，都是没错的，返回都是右值，且右值等同了
            return pHead2;
        }
        if(pHead2 == NULL){
            pHead2 = pHead1;
            return pHead1;
        }

        ListNode* current = (pHead1->val <= pHead2->val)?pHead1:pHead2;
        if(pHead1->val <= pHead2->val){
            pHead1->next = Merge(pHead1->next, pHead2);
        }else{
            pHead2->next = Merge(pHead1, pHead2->next);
        }
        return current;
    }
};
class Solution3 {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(pHead1 == NULL){
            return pHead2;
        }
        if(pHead2 == NULL){
            return pHead1;
        }

        ListNode* current = (pHead1->val <= pHead2->val)?pHead1:pHead2;
        if(pHead1->val <= pHead2->val){
            pHead1->next = Merge(pHead1->next, pHead2);
        }else{
            pHead2->next = Merge(pHead1, pHead2->next);
        }
        return current;
    }
};