leetcode——链表

160. 相交链表

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {set<ListNode*> s;ListNode* h = headA;while (h != NULL) {s.insert(h);h = h->next;}h = headB;while (h != NULL){if (s.find(h) != s.end()) {return h;}h = h->next;}return NULL;}
};

set存地址，模拟

206. 反转链表

class Solution {
public:ListNode* ans;void dfs(ListNode* pre, ListNode* now) {if (now->next == NULL) {now->next = pre;ans = now;return ;}dfs(now, now -> next);now->next = pre;}ListNode* reverseList(ListNode* head) {if (head == NULL) return NULL;if (head -> next == NULL) return head;dfs(head, head->next);head->next = NULL;return ans;}
};

递归模拟，注意head->next 要修改成 NULL 避免死循环

234. 回文链表

class Solution {
public:bool isPalindrome(ListNode* head) {vector<int> a;while (head != NULL) {a.push_back(head->val);head = head->next;}for (int i = 0, j = a.size() - 1; i < j; i++, j--) {if (a[i] != a[j]) return false;}return true;}
};

模拟

141. 环形链表

class Solution {
public:bool hasCycle(ListNode* head) {while (head != NULL) {if (head->val == 100001) return true;head->val = 100001;head = head->next;}return false;}
};

修改val做标记

142. 环形链表 II

class Solution {
public:ListNode* detectCycle(ListNode* head) {set<ListNode*> s;while (head != NULL) {if (s.count(head)) return head;s.insert(head);head = head->next;}return NULL;}
};

set模拟

21. 合并两个有序链表

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if (list1 == NULL) return list2;if (list2 == NULL) return list1;ListNode* ans = new ListNode();if (list1->val <= list2->val) ans = list1;else ans = list2;ListNode* h = new ListNode();while (list1 || list2) {if (!list1) {h->next = list2;list2 = list2->next;}else if (!list2) {h->next = list1;list1 = list1->next;}else {if (list1->val <= list2->val) {h->next = list1;list1 = list1->next;}else {h->next = list2;list2 = list2->next;}}h = h->next;}return ans;}
};

双指针模拟

2. 两数相加

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* h = new ListNode(0);ListNode* ans = h;int t = 0;while (l1 || l2) {ListNode* now = new ListNode(0);if (!l1) {int x = l2->val + t;now->val = x % 10;t = x / 10;l2 = l2->next;}else if (!l2) {int x = l1->val + t;now->val = x % 10;t = x / 10;l1 = l1->next;}else {int x = l1->val + l2->val + t;now->val = x % 10;t = x / 10;l1 = l1->next;l2 = l2->next;}h->next = now;h = h->next;}if (t) {h->next = new ListNode(t);}return ans->next;}
};

双指针模拟

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

class Solution {
public:int dfs(ListNode* now, int n) {if (now == NULL) return 0;int v = dfs(now->next, n) + 1;if (v == n + 1) {now->next = now->next->next;}return v;}ListNode* removeNthFromEnd(ListNode* head, int n) {int v = dfs(head, n);if (v == n) {head = head->next;}return head;}
};

dfs求链表层数，模拟

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

class Solution {
public:ListNode* swapPairs(ListNode* head) {if (head == NULL || head->next == NULL) return head;ListNode* ans = head->next;ListNode* l1 = head, * l2 = head->next;ListNode* pre = new ListNode(0, l1);while (l1 && l2) {pre->next = l2;l1->next = l2->next;l2->next = l1;swap(l1, l2);pre = l2;l1 = l2->next;if (l2->next == NULL) break;l2 = l2->next->next;}return ans;}
};

模拟

25. K 个一组翻转链表

class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {ListNode* dummy = new ListNode(0, head);ListNode* groupPre = dummy;while (true) {int kth = k;ListNode* cur = groupPre;while (kth && cur) {kth--;cur = cur->next;}if (!cur) break;ListNode* groupNext = cur->next;ListNode* pre = groupNext;cur = groupPre->next;ListNode* tmp = NULL;while (cur != groupNext) {tmp = cur->next;cur->next = pre;pre = cur;cur = tmp;}tmp = groupPre->next;groupPre->next = pre;groupPre = tmp;}return dummy->next;}
};

四个指针，groupPre、groupNext、pre、cur模拟

138. 随机链表的复制

class Solution {
public:Node* copyRandomList(Node* head) {Node* tmp = head;Node* dummy = new Node(0);dummy->next = head;Node* pre = dummy;map<Node*, Node*> mp;while (head) {Node* cur = new Node(head->val);pre->next = cur;mp[head] = cur;pre = cur;head = head->next;}head = tmp;tmp = dummy->next;while (head) {tmp->random = mp[head->random];tmp = tmp->next;head = head->next;}return dummy->next;}
};

map从源地址映射到新地址

148. 排序链表

class Solution {
public:ListNode* sortList(ListNode* head) {auto length = [](ListNode* head)->int {int ans = 0;while (head) {ans++;head = head->next;}return ans;};auto spiltList = [](ListNode* head, int step) -> ListNode* {ListNode* cur = head;for (int i = 0; i < step - 1 && cur; i++) {cur = cur->next;}if (!cur || cur->next == NULL) {return NULL;}ListNode* next_head = cur->next;cur->next = NULL;return next_head;};auto mergeList = [](ListNode* head1, ListNode* head2) -> pair<ListNode*, ListNode*> {ListNode* dummy = new ListNode(0);ListNode* cur = dummy;while (head1 && head2) {if (head1->val <= head2->val) {cur->next = head1;head1 = head1->next;}else {cur->next = head2;head2 = head2->next;}cur = cur->next;}while (head1) {cur->next = head1;head1 = head1->next;cur = cur->next;}while (head2) {cur->next = head2;head2 = head2->next;cur = cur->next;}return { dummy->next, cur };};int n = length(head);ListNode* dummy = new ListNode(0, head);for (int i = 2; i <= n; i *= 2) {ListNode* new_list_tail = dummy;ListNode* cur = dummy->next;while (cur) {ListNode* head1 = cur;ListNode* head2 = spiltList(head1, i);cur = spiltList(head2, i);auto [head, tail] = mergeList(head1, head2);new_list_tail->next = head;new_list_tail = tail;}}return dummy->next;}
};

迭代法归并排序

spiltList是断开链表并返回它的头节点

mergeList是合并两个链表并返回新链表的头尾节点

23. 合并 K 个升序链表

class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {ListNode* dummy = new ListNode();multiset<pair<int, ListNode*>> s;for (auto list : lists) {if (list) s.insert({ list->val, list });}ListNode* cur = dummy;while (s.size()) {auto it = s.begin();auto [x, list] = *it;s.erase(it);cur->next = list;cur = cur->next;list = list->next;if (list) {s.insert({ list->val, list });}}return dummy->next;}
};

优先队列模拟

146. LRU 缓存

class LRUCache {
public:int capacity = 0;int size = 0;unordered_map<int, int> mp;unordered_map<int, int> cnt;queue<int> q;LRUCache(int capacity) {this->capacity = capacity;}   int get(int key) {if (!cnt[key]) return -1;cnt[key]++;q.push(key);return mp[key];}void put(int key, int value) {if (size < capacity) {q.push(key);if (!cnt[key]) size++;cnt[key]++;}else {q.push(key);if (!cnt[key]) {while (true) {int x = q.front();q.pop();cnt[x]--;if (!cnt[x]) {break;}        }}cnt[key]++;}mp[key] = value;}
};