/**
 * 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é)點的鏈表解決問題
        // 待輸出鏈表的頭部
        ListNode* head = new ListNode;  //節(jié)點是個指針，需要new來開辟空間
        // 待輸出鏈表的 last 結(jié)點
        ListNode* last = head;   //last和head是一個東西，只是為了最后輸出的時候找到head
        while(l1 != nullptr && l2 != nullptr){  //循環(huán)條件
            if(l1->val < l2->val){
                last->next = l1;    //last->next指向l1
                l1 = l1->next;      //將l1的下一個節(jié)點改為l1
            }
            else{
                last->next = l2;
                l2 = l2->next;
            }
            last = last->next;   //將last的下一個節(jié)點改為last
        }
         // l1 或 l2 可能還有剩余結(jié)點沒有合并， 
        // 由于從上面的 while 循環(huán)中退出， 那么鏈表 l1 和 l2 至少有一個已經(jīng)遍歷結(jié)束
        if(l1 != nullptr){
            last->next = l1;
        }
        else if(l2 != nullptr){
            last->next = l2;
        }
        return head->next;
    }
};

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