算法 链表相关

将一个链表的前k个节点反转, 返回反转后的头节点

ListNode* reverseKList(ListNode* head, int k) {
    k--;
    ListNode* prev = nullptr;
    ListNode* cur = head;
    ListNode* next = head->next;
    while(k --)
    {
        cur->next = prev;
        prev = cur;
        cur = next;
        next = next->next;
    }
    cur->next = prev;
    head->next = next;
    return cur;
}

链表反转的每个操作需要关联三个节点, prev, cur, next, 这里没有做长度判断, list长度最少为2.

O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序

class Solution {
    ListNode* middleNode(ListNode* head) {
        ListNode* pre = head;
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            pre = slow; // 记录 slow 的前一个节点
            slow = slow->next;
            fast = fast->next->next;
        }
        pre->next = nullptr; // 断开 slow 的前一个节点和 slow 的连接
        return slow;
    }
    
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy; // 用哨兵节点简化代码逻辑
        ListNode* cur = &dummy; // cur 指向新链表的末尾
        while (list1 && list2) {
            if (list1->val < list2->val) {
                cur->next = list1; // 把 list1 加到新链表中
                list1 = list1->next;
            } else { // 注：相等的情况加哪个节点都是可以的
                cur->next = list2; // 把 list2 加到新链表中
                list2 = list2->next;
            }
            cur = cur->next;
        }
        cur->next = list1 ? list1 : list2; // 拼接剩余链表
        return dummy.next;
    }

public:
    ListNode* sortList(ListNode* head) {
        // 如果链表为空或者只有一个节点，无需排序
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        // 找到中间节点，并断开 head2 与其前一个节点的连接
        // 比如 head=[4,2,1,3]，那么 middleNode 调用结束后 head=[4,2] head2=[1,3]
        ListNode* head2 = middleNode(head);
        // 分治
        head = sortList(head);
        head2 = sortList(head2);
        // 合并
        return mergeTwoLists(head, head2);
    }
};

其实就是对链表进行归并排序, 每个链表的中点用快慢指针法最优找出, 然后分治划分空间, 回溯时左右两个区间的链表一定都是升序的, 排序问题就演变为合并升序链表.

复制随机链表

/*
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    unordered_map<Node*, Node*> cachedNode;
    Node* copyRandomList(Node* head) {
        if (head == nullptr) {
            return nullptr;
        }
        if (!cachedNode.count(head)) {
            Node* headNew = new Node(head->val);
            cachedNode[head] = headNew;
            headNew->next = copyRandomList(head->next);
            headNew->random = copyRandomList(head->random);
        }
        return cachedNode[head];
    }
};

这个是递归做法, 实际就是用一个哈希表保存所有原链表和新链表节点的对应, 如果原节点和新节点已有对应, 那么就是直接返回保存的新节点, 假如还没有新节点, 就造一个新节点.

LRC缓存, 存储键值对, 有容量限制, 超出容量删除使用最少的节点, 要求查询和插入都是O(1).

class LRUCache {
public:
    struct ListNode{
        int key, val;
        ListNode* next;
        ListNode* prev;
        
        ListNode(int k, int v)
            :key(k), val(v)
        {
            next = prev = nullptr;
        }
    };

    LRUCache(int capacity) {
        cap = capacity;
        cnt = 0;
    }
    
    int get(int key) {
        if(mp.count(key) == 0) return -1;
        // 把查询的节点头插回前面
        auto node = mp[key];
        int ret = node->val;
        push_front(node->key, node->val);
        erase(node);
        return ret;
    }
    
    void put(int key, int value) {
        if(!mp.count(key))  // 新插入
        {
            if(cnt == cap) 
            {
                int tmp = head->prev->key;
                erase(head->prev), cnt--;
                // 把mp中的对应删除
                mp.erase(tmp);
            }
            push_front(key, value);
            cnt++;
        }
        else  // 修改值
        {
            mp[key]->val = value;
            auto node = mp[key];
            push_front(node->key, node->val);
            erase(node);
        }
    }

    void push_front(int key, int value)
    {
        if(!head)
        {
            ListNode* newnode = new ListNode(key, value);
            newnode->next = newnode;
            newnode->prev = newnode;
            head = newnode;
            mp[key] = newnode;
            return;
        }

        ListNode* newnode = new ListNode(key, value);
        newnode->next = head;
        newnode->prev = head->prev;
        head->prev->next = newnode;
        head->prev = newnode;
        head = newnode;

        // 头插完顺便插入map
        mp[key] = newnode;
    }

    void erase(ListNode* cur)
    {
        cur->prev->next = cur->next;
        cur->next->prev = cur->prev;
    }

private:
    int cap;
    int cnt;
    ListNode* head = nullptr;
    unordered_map<int, ListNode*> mp; // key, 对应list中的指针
};

其实就是维护一个双向链表和一个哈希表, 哈希表和双向链表的插入都是O(1)(最优情况下), 利用双向链表做类似队列的操作, 哈希表存key和链表节点的映射, 查找时用哈希表O1找到链表节点, 将该节点从当前位置移到队头, 就可以使使用少的节点都往后排, 删除时就删队尾就行.