合并两个有序链表

1
class Solution {
2
public:
3
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
4
        // 1. 在栈上创建哨兵节点，方便统一操作
5
        ListNode dummy(0);
6
        ListNode *tail = &dummy;
7

8
        // 2. 先把两个链表简单粗暴地连起来
9
        for(ListNode *p = list1; p; p = p->next) tail = tail -> next = p;
10
        for(ListNode *p = list2; p; p = p->next) tail = tail -> next = p;
11

12
        // 3. 提取所有值并排序
13
        std::vector<int> vals;
14
        for(ListNode *p = dummy.next; p; p = p->next)
15
            vals.push_back(p->val);
16
        std::sort(vals.begin(), vals.end());
17

18
        // 4. 将排好序的值写回原节点
19
        ListNode *cur = dummy.next;
20
        for(int v : vals){
21
            cur -> val = v;
22
            cur = cur -> next;
23
        }
24
        return dummy.next;
25
    }
26
};

1
class Solution {
2
public:
3
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
4
        ListNode dummy(0);          // 哨兵头节点
5
        ListNode* tail = &dummy;    // 指向新链表的末尾
6

7
        // 归并核心：双指针比较
8
        while (l1 && l2) {
9
            if (l1->val < l2->val) {
10
                tail->next = l1;
11
                l1 = l1->next;
12
            } else {
13
                tail->next = l2;
14
                l2 = l2->next;
15
            }
16
            tail = tail->next;
17
        }
18

19
        // 拼接剩余段（当一条链走完，另一条链剩下的直接挂在尾部）
20
        tail->next = l1 ? l1 : l2;
21

22
        return dummy.next;
23
    }
24
};