合并有序链表

最近被问到了这个题，要求不能用额外空间，这个题的思路比较简单，由于是有序的就做一个遍历就可以，当时时间比较急写的解法代码行数较多不够简洁，再次记录一个简介的版本

用规约的话其实很容易实现，代码简洁，但是链表长度太长规约就会崩溃，再次只放递归的版本，自己面试的时候写的垃圾代码就不放了

struct Node{
    int val;
    Node *next;
    Node(int _v):val(_v),next(NULL){}
};

Node* mergeList(Node *l1,Node *l2){
    if(!l1) return l2;
    else if(!l2) return l1;

    Node* head = new Node(-1);
    Node* p = head;
    while(l1&&l2){
        if(l1->val<l2->val){
            p->next=l1;
            l1=l1->next;
        }else{
            p->next=l2;
            l2=l2->next;
        }
        p=p->next;
    }
    if(l1) p->next=l1;
    else if(l2) p->next=l2;

    return head->next;

}

自己写的复杂版本没有用到哨兵结点，导致需要分情况讨论，平白无故多了代码行数，添加哨兵后代码立马简洁很多，
不仅这道题，在众多链表题中哨兵结点都有着妙用，可以极大地减少边界条件的判断和代码的编写。