链表 典型习题
160 相交链表：遍历，统计是否出现过
/*** 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) {// 先把 A 链表的所有结点都访问一遍unordered_set<ListNode*> visited;ListNode* temp = headA;while (temp != nullptr) {visited.insert(temp);temp = temp->next;}temp = headB;while (temp != nullptr) {if (visited.count(temp)) {return temp;}visited.insert(temp);temp = temp->next;}return nullptr;}
};206 翻转链表：属于链表的基本操作之一
/*** 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* prev = nullptr;ListNode* curr = head;while (curr) {ListNode* next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;}
};234 回文链表
/*** 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> vals;while (head != nullptr) {vals.push_back(head->val);head = head->next;}for (int i = 0, j = (int)vals.size() - 1; i < j; ++i, --j) {if(vals[i] != vals[j]) {return false;}}return true;}
};141 环形链表
/*** 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 == NULL || head->next == NULL) return false;ListNode* fast = head->next;ListNode* slow = head;while (slow != fast) {if (fast == NULL || fast->next == NULL) return false;slow = slow->next;fast = fast->next->next;}return true;}
};142: 环形链表找起点：相遇之后复位再出发
a + n(b + c) = 2(a + b)
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast = head;ListNode* slow = head;while (true) {if (fast == nullptr || fast->next == nullptr) return nullptr;fast = fast->next->next;slow = slow->next;if (fast == slow) break;}fast = head;while (slow != fast) {fast = fast->next;slow = slow->next;}return fast;}
};
21: 合并两个有序链表
/*** 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* l1, ListNode* l2) {// 建立头节点ListNode* preHead = new ListNode(-1);// 建立 prevListNode* prev = preHead;// 添加更小的元素进来while (l1 != nullptr && l2 != nullptr) {if (l1->val < l2->val) {prev->next = l1;l1 = l1->next;} else {prev->next = l2;l2 = l2->next;}prev = prev->next;}prev->next = l1 == nullptr ? l2 : l1;return preHead->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(0, head);ListNode* second = dummy;ListNode* fast = head;for (int i = 0; i < n; ++i) {fast = fast->next;}while (fast!=nullptr) {second = second->next;fast = fast->next;}second->next = second->next->next;ListNode* ans = dummy->next;delete dummy;return ans;}
};25 K 个一组翻转链表
/*** 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:// head 和 tail 是实际上需要被翻转的链表的头节点和尾节点pair<ListNode*, ListNode*> myRev(ListNode* head, ListNode* tail) {ListNode* prev = tail->next;ListNode* p = head;while (prev != tail) {ListNode* nex = p->next;p->next = prev;prev = p;p = nex;}return {tail, head};}ListNode* reverseKGroup(ListNode* head, int k) {ListNode* hair = new ListNode(0, head);ListNode* pre = hair;while (head) {// 移动 tail k 步，到待翻转链表的尾部ListNode* tail = pre;for (int i = 0; i < k; i++) {tail = tail->next;if (!tail) {// 不足以翻转，则结束return hair->next;}}// 储存下一个节点，pre 已经有了ListNode* nex = tail->next;// 翻转pair<ListNode*, ListNode*> result = myRev(head, tail);// 取头和尾head = result.first;tail = result.second;// 链接pre->next = head;tail->next = nex;// 移动pre = tail;head = tail->next;}return hair->next;}
};146 LRU 缓存
# 定义一个存储数据的类
class DLinkedNode:def __init__(self, key = 0, value = 0):# 为什么要 key 和 value# 只有一个可以不？self.key = keyself.value = value# 之前前驱和后继的两个指针self.prev = Noneself.next = Noneclass LRUCache:def __init__(self, capacity: int):# 初始化容量self.capacity = capacityself.size = 0# 初始化头尾self.head = DLinkedNode()self.tail = DLinkedNode()# 初始化两者的关系self.head.next = self.tailself.tail.prev = self.head# 一个字典储存现在的数据self.cache = dict()def get(self, key: int) -> int:if key not in self.cache:return -1# 取值node = self.cache[key]# 把读取过的节点移动到头部self.moveToHead(node)return node.valuedef put(self, key: int, value: int) -> None:if key not in self.cache:# 生成新的节点node = DLinkedNode(key, value)# 赋值self.cache[key] = node# 把新加入的数据直接放到头部有self.addToHead(node)# 修改大小self.size += 1if self.size > self.capacity:removed = self.removeTail();self.cache.pop(removed.key)self.size -= 1else:# 取值node = self.cache[key]# 赋值node.value = value# 把读取过的节点移动到头部self.moveToHead(node)def addToHead(self, node):node.prev = self.headnode.next = self.head.nextself.head.next.prev = nodeself.head.next = nodedef removeNode(self, node):node.prev.next = node.nextnode.next.prev = node.prevdef moveToHead(self, node):# 先把节点摘掉self.removeNode(node)self.addToHead(node)def removeTail(self) -> DLinkedNode:node = self.tail.prevself.removeNode(node)return node# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)