/**
* 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;
}
};/**
* 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;
}
};/**
* 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;
}
};/**
* 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;
}
};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;
}
};
/**
* 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);
// 建立 prev
ListNode* 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;
}
};/**
* 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;
}
};/**
* 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;
}
};# 定义一个存储数据的类
class DLinkedNode:
def __init__(self, key = 0, value = 0):
# 为什么要 key 和 value
# 只有一个可以不？
self.key = key
self.value = value
# 之前前驱和后继的两个指针
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
# 初始化容量
self.capacity = capacity
self.size = 0
# 初始化头尾
self.head = DLinkedNode()
self.tail = DLinkedNode()
# 初始化两者的关系
self.head.next = self.tail
self.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.value
def 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 += 1
if self.size > self.capacity:
removed = self.removeTail();
self.cache.pop(removed.key)
self.size -= 1
else:
# 取值
node = self.cache[key]
# 赋值
node.value = value
# 把读取过的节点移动到头部
self.moveToHead(node)
def addToHead(self, node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def removeNode(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def moveToHead(self, node):
# 先把节点摘掉
self.removeNode(node)
self.addToHead(node)
def removeTail(self) -> DLinkedNode:
node = self.tail.prev
self.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)