23. 合并K个升序链表 (Hard)¶

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto cmp = [](ListNode* a, ListNode* b){
            return a->val > b->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq;
        for(auto head : lists){   //其实lists展示出的是head，而不是整条链表
            if(head){
                pq.push(head);
            }
        }

        ListNode dummy{};
        auto cur = &dummy;
        while(!pq.empty()){   //不能直接while(pq)
            auto node = pq.top();
            pq.pop();
            if(node -> next){
                pq.push(node->next);
            }
            cur->next = node;
            cur = cur->next;
        }
        return dummy.next;
    }
};

先创建一个最小堆，注意priority_queue的写法：先写一个cmp，然后把decltype设为他，然后就是把三个头节点放到最小堆里面；把最小的放在链表里即可。

21. 合并两个有序链表¶

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy{};
        auto cur = &dummy;

        while(list1 && list2){
            if(list1 -> val < list2 -> val){
                cur->next = list1;
                list1 = list1->next;
            }
            else{
                cur->next = list2;
                list2 = list2->next;
            }
            cur = cur->next;
        }
        cur->next = list1?list1:list2;
        return dummy.next;
    }
};

使用头插法，谁小就把下一个设为谁，最后拼接一下尾部即可。

206. 反转链表¶

c ListNode* reverseList(ListNode* head) { class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* cur = NULL; auto pre = head; while(pre){ auto tmp = pre->next; pre -> next = cur; cur = pre; pre = tmp; } return cur; } };

这个不用dummy啊，就是直接画一下图就行。