LeetCode——021

/*
21. Merge Two Sorted Lists My Submissions QuestionEditorial Solution
Total Accepted: 122136 Total Submissions: 345783 Difficulty: Easy
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Subscribe to see which companies asked this question
*/
/*
解题思路：
已排序好的双链表合并，是归并排序中一个基本函数。
总共分两步：
1.两个链表都有可比元素，取小前移
2.把剩余链表接到结果链表
*/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

        if(l1==NULL)return l2;
        if(l2==NULL)return l1;

        ListNode* dummy=new ListNode(-1);
        ListNode* p=dummy;
        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;
        if(l2)p->next=l2;
        //返回结果
        return dummy->next;

    }
};