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 = 0mult = 1while l1:num1 += l1.val * multmult *= 10l1 = l1.nextnum2 = 0mult = 1while l2:num2 += l2.val * multmult *= 10l2 = l2.nextsum = num1 + num2s = str(sum)s = reversed(s)dummy = ListNode()p = dummyfor i in s:p.next = ListNode(int(i))p = p.nextreturn dummy.next19. 删除链表的倒数第 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) {// 剩余部分长度不大于 kreturn 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>>::iteratorcache.splice(cache.begin(), cache, iter->second);// iter->second->second 是一个 valuereturn 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 是一个 keyhash.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; // 更新 valuereturn;}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; // 释放内存}}
};
