【LeetCode 热题 100】反转链表 / 回文链表 / 有序链表转换二叉搜索树 / LRU 缓存

⭐️个人主页：@小羊 ⭐️所属专栏：LeetCode 热题 100 很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~

---

相交链表

• 相交链表

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* cur1 = headA, *cur2 = headB;while (cur1 != cur2){cur1 == nullptr ? cur1 = headB : cur1 = cur1->next;cur2 == nullptr ? cur2 = headA : cur2 = cur2->next;}return cur1;}
};

---

反转链表

• 反转链表

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* prev = nullptr;ListNode* cur = head;while (cur){ListNode* next = cur->next;cur->next = prev;prev = cur;cur = next;} return prev;}
};

虽然上面这种方法更简单，但是相对来说不太好理解，如果新增一个虚拟头结点会清晰很多。

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* newhead = new ListNode;ListNode* cur = head;while (cur){ListNode* next = cur->next;cur->next = newhead->next;newhead->next = cur;cur = next;} cur = newhead->next;delete newhead;return cur;}
};

---

回文链表

• 回文链表

首先用快慢指针找到中间节点，反转后半部分链表，然后逐个遍历比较两个链表是否所有值都相等。
需要注意的是，如果原链表节点个数为奇数，则后本部分会比前半部分多一个节点，因此我们最后需要判断的是遍历后半部分链表的指针最后是否为空。

class Solution {
public:bool isPalindrome(ListNode* head) {ListNode* fast = head, *slow = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}// 翻转后半部分ListNode* prev = nullptr;while (slow){ListNode* next = slow->next;slow->next = prev;prev = slow;slow = next;}// 比较是否回文ListNode* cur1 = head, *cur2 = prev;while (cur1 && cur2 && cur1->val == cur2->val){cur1 = cur1->next;cur2 = cur2->next;}return cur2 == nullptr;}
};

---

环形链表

• 环形链表

链表类经典判环问题，通常用快慢双指针解决。

class Solution {
public:bool hasCycle(ListNode *head) {ListNode* fast = head, *slow = head;while (fast && fast->next){fast = fast->next->next;slow = slow->next;if (fast == slow) return true;}return false;}
};

---

环形链表 II

• 环形链表 II

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast = head, *slow = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (fast == slow){while (head != fast){head = head->next;fast = fast->next;}return fast;}}return nullptr;}
};

---

合并两个有序链表

• 合并两个有序链表

合并两个有序链表，这个过程是重复的递归过程。

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);}else{list2->next = mergeTwoLists(list1, list2->next);}return list1->val < list2->val ? list1 : list2;}
};

---

两数相加

• 两数相加

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {int t = 0;ListNode* newhead = new ListNode();ListNode* tail = newhead;while (l1 || l2){if (l1){t += l1->val;l1 = l1->next;}if (l2){t += l2->val;l2 = l2->next;}tail->next = new ListNode(t % 10);t /= 10;tail = tail->next;}if (t) tail->next = new ListNode(t);tail = newhead->next;delete newhead;return tail;}
};

---

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

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

第一次没用虚拟头结点，搞了半天过不去，半天才反应过来还有删除头节点的可能🤡…

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode *newhead = new ListNode(0, head);ListNode *l = newhead, *r = head;while (n--) r = r->next;while (r){r = r->next;l = l->next;}l->next = l->next->next;head = newhead->next;return head;}
};

---

两两交换链表中的节点

• 两两交换链表中的节点

方法一：用多个指针标记节点。

class Solution {
public:ListNode* swapPairs(ListNode* head) {if (head == nullptr || head->next == nullptr) return head; ListNode *newhead = new ListNode(0, head);ListNode *tail = newhead, *cur1 = head, *cur2 = cur1->next, *cur3 = cur2->next;while (cur1 && cur1->next){tail->next = cur2;cur1->next = cur3;cur2->next = cur1;tail = cur1;cur1 = cur3;if (cur1) cur2 = cur1->next;if (cur2) cur3 = cur2->next;}tail = newhead->next;delete newhead;return tail;}
};

方法二：递归。

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;}
};

方法三：最常想到的方法。

class Solution {
public:ListNode* swapPairs(ListNode* head) {if (head == nullptr || head->next == nullptr) return head;ListNode *newhead = new ListNode(0, head);ListNode *tail = newhead, *cur = head;while (cur && cur->next){ListNode *next = cur->next->next;tail->next = cur->next;cur->next->next = cur;cur->next = next;tail = cur;cur = next;}tail = newhead->next;delete newhead;return tail;}
};

---

K 个一组翻转链表

• K 个一组翻转链表

• 先求出链表的长度，计算能反转多少组；
• 循环反转链表操作，注意每组结束尾节点都需要变换。

class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {ListNode* cur = head;int len = 0;while (cur){len++;cur = cur->next;}len /= k;cur = head;ListNode *newhead = new ListNode;ListNode *tail = newhead;for (int i = 0; i < len; i++){ListNode *tmp = cur;for (int j = 0; j < k; j++){ListNode *next = cur->next;cur->next = tail->next;tail->next = cur;cur = next;}tail = tmp;}tail->next = cur;tail = newhead->next;delete newhead;return tail;}
};

---

随机链表的复制

• 随机链表的复制

遍历新建链表，过程中建立节点间的映射关系；第二次遍历链表，根据链表的映射关系就能找到随机指针指向的节点。

class Solution {
public:Node* copyRandomList(Node* head) {unordered_map<Node*, Node*> map;Node *newhead = nullptr, *tail = nullptr, *cur = head;while (cur){if (tail == nullptr){newhead = tail = new Node(cur->val);}else{tail->next = new Node(cur->val);tail = tail->next;}map[cur] = tail;cur = cur->next;}cur = head;tail = newhead;while (cur){if (cur->random == nullptr) {tail->random = nullptr;}else{tail->random = map[cur->random];}cur = cur->next;tail = tail->next;}return newhead;}
};

---

排序链表

• 排序链表

class Solution {
public:ListNode* sortList(ListNode* head) {if (head == nullptr) return head;int len = 0;ListNode *cur = head;while (cur){len++;cur = cur->next;}return merge(head, len);}ListNode* merge(ListNode* head, int len){if (len == 1) return head;int halflen = len / 2;ListNode *tail = head;for (int i = 0; i < halflen - 1; i++) // 边界情况，2个节点{tail = tail->next;}ListNode *nexthead = tail->next;tail->next = nullptr; // 断开链表ListNode *cur1 = merge(head, halflen);ListNode *cur2 = merge(nexthead, len - halflen);return sort(cur1, cur2);}ListNode* sort(ListNode* l1, ListNode* l2){ListNode node;ListNode *tail = &node;while (l1 && l2){if (l1->val < l2->val){tail->next = l1;l1 = l1->next;}else{tail->next = l2;l2 = l2->next;}tail = tail->next;}if (l1) tail->next = l1;if (l2) tail->next = l2;return node.next;}
};

---

合并 K 个升序链表

• 合并 K 个升序链表

优先级队列.

class Solution {struct cmp{bool operator()(const ListNode *l1, const ListNode *l2){return l1->val > l2->val;}};
public:ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*, vector<ListNode*>, cmp> pq;for (auto &e : lists) if (e) pq.push(e);ListNode node;ListNode *tail = &node;while (pq.size()){tail->next = pq.top();pq.pop();tail = tail->next;if (tail->next) pq.push(tail->next);}return node.next;}
};

分治

class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {return merge(lists, 0, lists.size() - 1);}ListNode* merge(vector<ListNode*>& lists, int l, int r){if (l > r) return nullptr;if (l == r) return lists[l];int mid = (l + r) >> 1;return merge2Lists(merge(lists, l, mid), merge(lists, mid + 1, r));}ListNode* merge2Lists(ListNode* l1, ListNode* l2){if (l1 == nullptr) return l2;if (l2 == nullptr) return l1;if (l1->val < l2->val){l1->next = merge2Lists(l1->next, l2);return l1;}else{l2->next = merge2Lists(l1, l2->next);return l2;}}
};

---

有序链表转换二叉搜索树

• 有序链表转换二叉搜索树

class Solution {
public:TreeNode* sortedListToBST(ListNode* head) {int len = 0;ListNode *cur = head;while (cur){len++;cur = cur->next;}return buildBST(head, 0, len - 1);}TreeNode* buildBST(ListNode*& head, int l, int r){if (l > r) return nullptr;int mid = l + (r - l) / 2;TreeNode *left = buildBST(head, l, mid - 1);TreeNode *root = new TreeNode(head->val);root->left = left;head = head->next;root->right = buildBST(head, mid + 1, r);return root;}
};

---

LRU 缓存

• LRU 缓存

class LRUCache {struct listnode{int key, value;listnode* prev;listnode* next;listnode(int k = 0, int v = 0) : key(k), value(v), prev(nullptr), next(nullptr){}};
public:LRUCache(int capacity) : _capacity(capacity), _size(0){_head = new listnode;_tail = new listnode;_head->next = _tail;_tail->prev = _head;}// 引入头尾两个虚拟节点，方便头插和尾删，头尾指针不用修改指向int get(int key) {if (!_cache.count(key)){return -1;}else{listnode* node = _cache[key];move2head(node);return node->value;}}void put(int key, int value) {if (!_cache.count(key)){listnode* newnode = new listnode(key, value);_cache[key] = newnode;_size++;add2head(newnode);if (_size > _capacity){removetail();}}else{listnode* node = _cache[key];node->value = value;move2head(node);}}void add2head(listnode* node){node->next = _head->next;_head->next->prev = node;_head->next = node;node->prev = _head;}void move2head(listnode* node){node->prev->next = node->next;node->next->prev = node->prev;add2head(node);}void removetail(){listnode* tail = _tail->prev;tail->prev->next = tail->next;tail->next->prev = tail->prev;_cache.erase(tail->key);delete tail;_size--;}    
private:int _size;int _capacity;listnode* _head;listnode* _tail;unordered_map<int, listnode*> _cache;
};

---

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~