LeetCode Hot 100：链表

UestcXiye

已于 2024-10-22 14:19:55 修改

阅读量448

点赞数 5

分类专栏： Every day a LeetCode 文章标签： C++ LeetCode 数据结构与算法

于 2024-10-20 16:14:16 首次发布

本文链接：https://blog.csdn.net/ProgramNovice/article/details/143084439

版权

Every day a LeetCode 专栏收录该内容

550 篇文章

订阅专栏

LeetCode Hot 100：链表

160. 相交链表

思路 1：双指针

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        if (headA == nullptr || headB == nullptr)
            return nullptr;

        ListNode* pA = headA;
        ListNode* pB = headB;

        while (pA != pB) {
            pA = pA == nullptr ? headB : pA->next;
            pB = pB == nullptr ? headA : pB->next;
        }

        return pA;
    }
};

思路 2：哈希集合

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        unordered_set<ListNode*> visited;
        ListNode* p = headA;
        while (p) {
            visited.insert(p);
            p = p->next;
        }

        p = headB;
        while (p) {
            if (visited.count(p))
                return p;
            p = p->next;
        }

        return nullptr;
    }
};

206. 反转链表

思路 1：迭代

/**
 * 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* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* nxt = nullptr;

        while (cur) {
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }

        return pre;
    }
};

思路 2：递归

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr; // 如果忽略了这一点，链表中可能会产生环
        return newHead;
    }
};

思路 3：辅助数组

/**
 * 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* reverseList(ListNode* head) {
        ListNode* p = head;
        vector<int> arr;
        while (p) {
            arr.push_back(p->val);
            p = p->next;
        }
        int i = arr.size() - 1;
        p = head;
        while (p) {
            p->val = arr[i];
            i--;
            p = p->next;
        }
        return head;
    }
};

234. 回文链表

思路 1：辅助数组 + 双指针

/**
 * 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:
    bool isPalindrome(ListNode* head) {
        vector<int> arr;
        ListNode* p = head;
        while (p) {
            arr.push_back(p->val);
            p = p->next;
        }

        int i = 0, j = arr.size() - 1;
        while (i <= j) {
            if (arr[i] != arr[j])
                return false;
            i++;
            j--;
        }

        return true;
    }
};

思路 2：寻找中间节点 + 反转链表

/**
 * 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:
    bool isPalindrome(ListNode* head) {
        ListNode* mid = middleNode(head);
        ListNode* head2 = reverseList(mid);
        while (head2) {
            if (head->val != head2->val)
                return false;
            head = head->next;
            head2 = head2->next;
        }
        return true;
    }
    // 876. 链表的中间结点
    ListNode* middleNode(ListNode* head) {
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    // 206. 反转链表
    ListNode* reverseList(ListNode* head) {
        ListNode *pre = nullptr, *cur = head;
        while (cur) {
            ListNode* nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
};

141. 环形链表

思路 1：快慢指针

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return false;

        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast)
                break;
        }

        return slow == fast;
    }
};

思路 2：哈希集合

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode* head) {
        unordered_set<ListNode*> hashSet;
        ListNode* p = head;
        while (p) {
            if (hashSet.find(p) != hashSet.end())
                return true;
            hashSet.insert(p);
            p = p->next;
        }

        return false;
    }
};

142. 环形链表 II

思路 1：哈希集合

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        unordered_set<ListNode*> hashSet;
        ListNode* p = head;
        while (p) {
            if (hashSet.find(p) != hashSet.end())
                return p;
            hashSet.insert(p);
            p = p->next;
        }

        return nullptr;
    }
};

思路 2：快慢指针

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return nullptr;

        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                ListNode* p = head;
                while (p != slow) {
                    p = p->next;
                    slow = slow->next;
                }
                return p;
            }
        }

        return nullptr;
    }
};

21. 合并两个有序链表

思路 1：双指针

/**
 * 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* list1, ListNode* list2) {
        if (list1 == nullptr)
            return list2;
        if (list2 == nullptr)
            return list1;

        ListNode *p1 = list1, *p2 = list2;
        ListNode* dummy = new ListNode();
        ListNode* p = dummy;

        while (p1 && p2) {
            if (p1->val < p2->val) {
                p->next = p1;
                p1 = p1->next;
            } else {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }

        if (p1)
            p->next = p1;
        if (p2)
            p->next = p2;

        return dummy->next;
    }
};

思路 2：递归

/**
 * 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* list1, ListNode* list2) {
        if (list1 == nullptr)
            return list2;
        if (list2 == nullptr)
            return list1;

        if (list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

2. 两数相加

思路 1：迭代

/**
 * 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode();
        ListNode* cur = dummy;
        int add = 0; // 进位

        while (l1 || l2 || add) {
            int d1 = l1 ? l1->val : 0;
            int d2 = l2 ? l2->val : 0;
            int sum = d1 + d2 + add;
            ListNode* nxt = new ListNode(sum % 10);
            cur->next = nxt;
            cur = nxt;
            add = sum / 10;
            if (l1)
                l1 = l1->next;
            if (l2)
                l2 = l2->next;
        }

        return dummy->next;
    }
};

思路 2：模拟

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        num1 = 0
        mult = 1
        while l1:
            num1 += l1.val * mult
            mult *= 10
            l1 = l1.next
        
        num2 = 0
        mult = 1
        while l2:
            num2 += l2.val * mult
            mult *= 10
            l2 = l2.next
        
        sum = num1 + num2
        s = str(sum)
        s = reversed(s)
        
        dummy = ListNode()
        p = dummy
        for i in s:
            p.next = ListNode(int(i))
            p = p.next
        
        return dummy.next

19. 删除链表的倒数第 N 个结点

思路 1：快慢指针

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode();
        dummy->next = head;
        ListNode* fast = head;
        ListNode* slow = dummy;
        for (int i = 0; i < n; i++)
            fast = fast->next;
        while (fast) {
            fast = fast->next;
            slow = slow->next;
        }
        // slow->next 就是要删除的节点
        ListNode* delNode = slow->next;
        slow->next = delNode->next;
        delNode->next = nullptr;
        delete delNode;

        return dummy->next;
    }
};

思路 2：栈

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode();
        dummy->next = head;
        stack<ListNode*> stk;
        ListNode* cur = dummy;
        while (cur) {
            stk.push(cur);
            cur = cur->next;
        }
        for (int i = 0; i < n; i++)
            stk.pop();
        ListNode* prev = stk.top();
        ListNode* delNode = prev->next;
        prev->next = delNode->next;
        delNode->next = nullptr;
        delete delNode;
        return dummy->next;
    }
};

思路 3：计算链表长度

/**
 * 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 {
private:
    int getListLength(ListNode* head) {
        int len = 0;
        ListNode* p = head;
        while (p) {
            len++;
            p = p->next;
        }
        return len;
    }

public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode();
        dummy->next = head;
        ListNode* p = dummy;
        int len = getListLength(head);
        for (int i = 0; i < len - n; i++)
            p = p->next;
        ListNode* delNode = p->next;
        p->next = delNode->next;
        delNode->next = nullptr;
        delete delNode;
        return dummy->next;
    }
};

24. 两两交换链表中的节点

思路 1：递归

/**
 * 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* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;

        ListNode* newHead = head->next;
        head->next = swapPairs(newHead->next);
        newHead->next = head;
        return newHead;
    }
};

思路 2：迭代

/**
 * 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* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;

        ListNode* dummy = new ListNode();
        dummy->next = head;
        ListNode* p = dummy;

        while (p->next && p->next->next) {
            ListNode *n1 = p->next, *n2 = n1->next;
            p->next = n2;
            n1->next = n2->next;
            n2->next = n1;
            p = n1;
        }

        return dummy->next;
    }
};

25. K 个一组翻转链表

思路 1：模拟

/**
 * 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* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode();
        dummy->next = head;
        ListNode* pre = dummy;

        while (head) {
            ListNode* tail = pre;
            for (int i = 0; i < k; i++) {
                tail = tail->next;
                if (tail == nullptr) {
                    // 剩余部分长度不大于 k
                    return dummy->next;
                }
            }
            ListNode* nxt = tail->next;
            pair<ListNode*, ListNode*> p = reverseList(head, tail);
            head = p.first;
            tail = p.second;

            pre->next = head;
            tail->next = nxt;
            pre = tail;
            head = tail->next;
        }

        return dummy->next;
    }
    pair<ListNode*, ListNode*> reverseList(ListNode* head, ListNode* tail) {
        ListNode* prev = tail->next;
        ListNode* p = head;
        while (prev != tail) {
            ListNode* nxt = p->next;
            p->next = prev;
            prev = p;
            p = nxt;
        }
        return {tail, head};
    }
};

138. 随机链表的复制

思路 1：迭代 + 哈希

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr)
            return nullptr;

        Node* curNode = head;
        unordered_map<Node*, Node*> hash; // <原结点，新结点>
        // 复制各节点，建立 “原节点 -> 新节点” 的哈希映射
        while (curNode) {
            hash[curNode] = new Node(curNode->val);
            curNode = curNode->next;
        }
        curNode = head;
        while (curNode) {
            hash[curNode]->next = hash[curNode->next];
            hash[curNode]->random = hash[curNode->random];
            curNode = curNode->next;
        }
        // 返回新链表的头节点
        return hash[head];
    }
};

思路 2：递归 + 哈希

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
private:
    unordered_map<Node*, Node*> hashMap; // <原结点，新结点>
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr)
            return nullptr;

        if (hashMap.find(head) == hashMap.end()) {
            Node* newHead = new Node(head->val);
            hashMap[head] = newHead;
            newHead->next = copyRandomList(head->next);
            newHead->random = copyRandomList(head->random);
        }

        return hashMap[head];
    }
};

148. 排序链表

思路 1：辅助数组

/**
 * 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* sortList(ListNode* head) {
        if (head == nullptr)
            return nullptr;

        ListNode* p = head;
        vector<int> arr;
        while (p) {
            arr.push_back(p->val);
            p = p->next;
        }
        sort(arr.begin(), arr.end());
        p = head;
        for (int i = 0; i < arr.size(); i++) {
            p->val = arr[i];
            p = p->next;
        }
        return head;
    }
};

思路 2：自顶向下归并排序

/**
 * 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* sortList(ListNode* head) { return sortList(head, nullptr); }
    // 辅函数 - 给定头尾指针，进行归并排序
    ListNode* sortList(ListNode* head, ListNode* tail) {
        if (head == nullptr)
            return head;
        if (head->next == tail) {
            head->next = nullptr;
            return head;
        }
        ListNode *slow = head, *fast = head;
        while (fast != tail) {
            slow = slow->next;
            fast = fast->next;
            if (fast != tail)
                fast = fast->next;
        }
        ListNode* mid = slow;
        return merge(sortList(head, mid), sortList(mid, tail));
    }
    // 辅函数 - 按升序合并两个链表
    ListNode* merge(ListNode* head1, ListNode* head2) {
        ListNode *dummy = new ListNode();
        ListNode *p = dummy;
        ListNode *p1 = head1, *p2 = head2;
        while (p1 && p2) {
            if (p1->val < p2->val) {
                p->next = p1;
                p1 = p1->next;
            } else {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }
        p->next = p1 ? p1 : p2;
        return dummy->next;
    }
};

23. 合并 K 个升序链表

思路 1：优先队列

/**
 * 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 {
private:
    struct Comp {
        bool operator()(ListNode* l1, ListNode* l2) {
            return l1->val > l2->val;
        }
    };

public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty())
            return nullptr;

        priority_queue<ListNode*, vector<ListNode*>, Comp> pq;
        for (ListNode* list : lists)
            if (list != nullptr)
                pq.push(list);

        ListNode* dummy = new ListNode();
        ListNode* p = dummy;
        while (!pq.empty()) {
            p->next = pq.top();
            pq.pop();
            p = p->next;
            if (p->next)
                pq.push(p->next);
        }

        return dummy->next;
    }
};

思路 2：顺序合并

/**
 * 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 {
private:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr)
            return list2;
        if (list2 == nullptr)
            return list1;

        ListNode* dummy = new ListNode();
        ListNode* p = dummy;
        ListNode *p1 = list1, *p2 = list2;
        while (p1 && p2) {
            if (p1->val < p2->val) {
                p->next = p1;
                p1 = p1->next;
            } else {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }
        p->next = p1 ? p1 : p2;

        return dummy->next;
    }

public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* ans = nullptr;
        for (size_t i = 0; i < lists.size(); i++)
            ans = mergeTwoLists(ans, lists[i]);
        return ans;
    }
};

思路 3：分治合并

/**
 * 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 {
private:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr)
            return list2;
        if (list2 == nullptr)
            return list1;

        ListNode* dummy = new ListNode();
        ListNode* p = dummy;
        ListNode *p1 = list1, *p2 = list2;
        while (p1 && p2) {
            if (p1->val < p2->val) {
                p->next = p1;
                p1 = p1->next;
            } else {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }
        p->next = p1 ? p1 : p2;

        return dummy->next;
    }
    ListNode* merge(vector<ListNode*>& lists, int left, int right) {
        if (left == right)
            return lists[left];
        if (left > right)
            return nullptr;
        int mid = left + (right - left) / 2;
        return mergeTwoLists(merge(lists, left, mid),
                             merge(lists, mid + 1, right));
    }

public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
};

146. LRU 缓存

思路 1：哈希表 + 链表

class LRUCache {
private:
    int size;
    unordered_map<int, list<pair<int, int>>::iterator> hash;
    list<pair<int, int>> cache; // <key, value>

public:
    LRUCache(int capacity) : size(capacity) {

    }
    
    int get(int key) {
        auto iter = hash.find(key);
        if (iter == hash.end())
            return -1;
        // iter->second 是一个 list<pair<int, int>>::iterator
        cache.splice(cache.begin(), cache, iter->second);
        // iter->second->second 是一个 value
        return iter->second->second;
    }
    
    void put(int key, int value) {
        auto iter = hash.find(key);
        if (iter != hash.end())
        {
            iter->second->second = value;
            cache.splice(cache.begin(), cache, iter->second);
            return;
        }
        cache.insert(cache.begin(), pair<int, int>(key, value));
        hash[key] = cache.begin();
        if (cache.size() > size)
        {
            // cache.back().first 是一个 key
            hash.erase(cache.back().first);
            cache.pop_back();
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

思路 2：哈希表 + 自定义双向链表

class Node {
public:
    int key, value;
    Node *prev, *next;

    Node(int k = 0, int v = 0) : key(k), value(v) {}
};

class LRUCache {
private:
    int capacity;
    Node* dummy; // 哨兵节点
    unordered_map<int, Node*> key_to_node;

    // 删除一个节点（抽出一本书）
    void remove(Node* x) {
        x->prev->next = x->next;
        x->next->prev = x->prev;
    }

    // 在链表头添加一个节点（把一本书放在最上面）
    void push_front(Node* x) {
        x->prev = dummy;
        x->next = dummy->next;
        x->prev->next = x;
        x->next->prev = x;
    }

    Node* get_node(int key) {
        auto it = key_to_node.find(key);
        if (it == key_to_node.end()) // 没有这本书
            return nullptr;
        auto node = it->second; // 有这本书
        remove(node);           // 把这本书抽出来
        push_front(node);       // 放在最上面
        return node;
    }

public:
    LRUCache(int capacity) : capacity(capacity), dummy(new Node()) {
        dummy->prev = dummy;
        dummy->next = dummy;
    }

    int get(int key) {
        auto node = get_node(key);
        return node ? node->value : -1;
    }

    void put(int key, int value) {
        auto node = get_node(key);
        if (node) {              // 有这本书
            node->value = value; // 更新 value
            return;
        }
        key_to_node[key] = node = new Node(key, value); // 新书
        push_front(node);                               // 放在最上面
        if (key_to_node.size() > capacity) {            // 书太多了
            auto back_node = dummy->prev;
            key_to_node.erase(back_node->key);
            remove(back_node); // 去掉最后一本书
            delete back_node;  // 释放内存
        }
    }
};