/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // 使用帶頭結(jié)點(diǎn)的鏈表解決問題
        // 待輸出鏈表的頭部
        ListNode* head = new ListNode;  //節(jié)點(diǎn)是個(gè)指針，需要new來開辟空間
        // 待輸出鏈表的 last 結(jié)點(diǎn)
        ListNode* last = head;   //last和head是一個(gè)東西，只是為了最后輸出的時(shí)候找到head
        while(l1 != nullptr && l2 != nullptr){  //循環(huán)條件
            if(l1->val < l2->val){
                last->next = l1;    //last->next指向l1
                l1 = l1->next;      //將l1的下一個(gè)節(jié)點(diǎn)改為l1
            }
            else{
                last->next = l2;
                l2 = l2->next;
            }
            last = last->next;   //將last的下一個(gè)節(jié)點(diǎn)改為last
        }
         // l1 或 l2 可能還有剩余結(jié)點(diǎn)沒有合并， 
        // 由于從上面的 while 循環(huán)中退出， 那么鏈表 l1 和 l2 至少有一個(gè)已經(jīng)遍歷結(jié)束
        if(l1 != nullptr){
            last->next = l1;
        }
        else if(l2 != nullptr){
            last->next = l2;
        }
        return head->next;
    }
};

struct ListNode {
       int val;    //定義val變量值，存儲(chǔ)節(jié)點(diǎn)值
       struct ListNode *next;   //定義next指針，指向下一個(gè)節(jié)點(diǎn)，維持節(jié)點(diǎn)連接
  }