链表(归并排序)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        auto dummy = new ListNode(-1);//先定义一个虚拟头节点，值随便赋一个
        auto tail = dummy;//定义个尾指针，来指新链表的尾节点
        while(l1!=NULL && l2!=NULL)//如果l1,l2所指节点都不为空
        {
            if(l1->val < l2->val)  //当l1节点的值小于l2的值
            {
                tail = tail->next =l1;//新链表尾节点=原先尾节点的下一个点=l1
                l1=l1->next;// l1被用了指针指向下一个节点，并使其尾l1
            }
            else
            {
                tail = tail->next =l2;//同上
                l2 = l2->next;
            }
        }
        if(l1!=NULL)//当最后只剩一个节点必定是最大的节点，如果是l1里的，则最后的尾节点=l1
        tail->next = l1;
        if(l2!=NULL)
        tail->next = l2;//否则为l2

        return dummy->next;//返回真实头节点，即虚拟头节点的下一个点
    }
};