链表

链表是最基本的包含地址信息的数据结构。

单链表的节点拥有的地址信息是下一个节点的位置，那么从整体来看可以是一个手链状的结构，可从个体来看，一个节点一个孤独的存储在磁盘空间的信息。

翻转链表

原地翻转链表，需要将相邻的两个节点的位置关系改变，比如原先节点的位置关系是t1->next = t2，那么为了翻转链表，就需要将t2的下一个元素为t1，那么只需要让t2->next = t1就行。为了保存链表接下来的信息：原先t2->next后的内容预先用一个变量节点来保存

ListNode* reverseList(ListNode* head) {
        if(head == nullptr) return head;
        ListNode* t1 = head , *t2 = head->next;
        while(t2){
            ListNode* t3 = t2->next;
            t2->next = t1;
            t1 = t2 , t2 = t3;
        }        
        head->next = nullptr;
        return t1;
    }

合并K个升序链表

合并K个升序链表，需要将每个链表的第一个节点比较大小后选择插入，并且将该节点的后一个节点放入排序中，从而达成遍历所有链表的目标

排序的方式有很多，如果是取出使用sort，那么k k n ，如果是使用堆的数据结构，那么排序为n log k，所以使用小根堆

ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode dummy;
        ListNode* cur = &dummy;
        auto cmp = [](ListNode* l1 , ListNode* l2){
            return l1->val > l2->val;
        };
        priority_queue<ListNode*,vector<ListNode*>,decltype(cmp)> min_heap(cmp);
        for(auto list : lists){
            if(list) min_heap.push(list);
        }
        while(!min_heap.empty())
        {
            auto node = min_heap.top();
            min_heap.pop();
            cur->next = node;
            if(node->next) min_heap.push(node->next);
            cur = cur->next;
        }
        return dummy.next;
    }