[数据结构与算法]36. 合并两个排序的链表(DAY 27)

原题题目

先理解再做题，代码就是把思想给写出来。可以先写个大概，然后自己再debug。

代码实现

/**
 * 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), tail=dummy;
        while(l1&&l2)
        {
            if(l1->val<l2->val)
            {
                tail=tail->next=l1;
                l1=l1->next;
            }
            else 
            {
                tail=tail->next=l2;
                l2=l2->next;
            }
            
        }
        if(l1)tail->next=l1;
        if(l2)tail->next=l2;
        
        return dummy->next;
    }
    
    
    
};

解题思路

先定义一个虚拟头节点dummy ，尾结点等于这个变量dummy。
当 l1、l2都不为空时，看l1和l2的值，如果l1<l2 就把l1接过去，l1=l1->next 把l1往后移动一位。 else 就把l2接到尾部，l2=l2->next。
最后，如果l1剩余，if(l1) 就把l1接到尾结点，如果l2存在，tail->next=l2
这两个最多只有一个成立。
返回虚拟头节点的下一个。