目录
建立链表
访问链表
删除节点
相交链表
反转链表
回文链表
环形链表
环形链表 II
两数相加
删除链表的倒数第N个节点
两两交换链表中的节点
随机链表的复制
排序链表
N个一体翻转链表
K个一组翻转链表
合并两个有序链表
合并K个升序链表
双向链表+哈希表 LRU
Main
建立链表
链表节点结构
struct Node {int value = 0;Node *next = nullptr;
};从一个数组里面取元素返回链表，如果数组是空返回空指针，不带头节点的链表，意味着第一个元素需要放到head指针里面去，然后从第二个元素开始放到链表尾，不断更新链表尾
Node *vectorTOList(std::vector<int> nums) {if (nums.empty())return nullptr;Node *head = new Node();head->value = nums[0];Node *cur = head;for (int i = 1; i < nums.size(); ++i) {cur->next = new Node{nums[i], nullptr};cur = cur->next;}return head;
}访问链表
如果链表是空的直接返回，输出当前节点的值，更新当前节点
void showList(Node *head) {if (head == nullptr)return;while (head) {std::cout << head->value << ' ';head = head->next;}std::cout << '\n';
}删除节点
删除指针指向的节点，用后驱节点的值覆盖该节点，释放后驱节点
void deleteNode(Node*p) {if(p==nullptr)return;if(p->next==nullptr) {delete p;return;}Node*temp=p->next;p->next=temp->next;p->value=temp->value;delete temp;
}相交链表
160. 相交链表 - 力扣（LeetCode）
记A链表=a+c，B链表=b+c，要找到c的起始节点
让一个指针走a+c+b，另一个指针走b+c+a，此时这两个指针都指向c
/*** 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) {ListNode *pa = headA, *pb = headB;while (pa != pb) {pa = pa ? pa->next : headB;pb = pb ? pb->next : headA;}return pa;}
};反转链表
206. 反转链表 - 力扣（LeetCode）
先记录前一个节点和后一个节点的指针，然后把当前节点的后驱节点更新为前节点，继续操作后一个节点
/*** 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* cur) {ListNode* prev = nullptr;while (cur) {ListNode* next = cur->next;cur->next = prev;prev = cur;cur = next;}return prev;}
};回文链表
234. 回文链表 - 力扣（LeetCode）
简单的可以取出来放到数组里面，然后从头尾一起走比较，这需要额外的空间
如果要原地比较，先用快慢指针找出中间节点，翻转后面一半节点，从中间和起始一起走比较
/*** 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> values;ListNode* p = head;while (p) {values.push_back(p->val);p = p->next;}for (int i = 0, j = values.size() - 1; i < j; i++, j--) {if (values[i] != values[j])return false;}return true;}
};环形链表
141. 环形链表 - 力扣（LeetCode）
用快慢指针走，如果有环两个指针会相遇，没环快指针能走完
/*** 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* fast = head->next;ListNode* slow = head;while (fast != slow) {if (fast == nullptr || fast->next == nullptr)return false;fast = fast->next->next;slow = slow->next;}return true;}
};环形链表 II
142. 环形链表 II - 力扣（LeetCode）
287. 寻找重复数 - 力扣（LeetCode）
先用快慢指针判断有没有环，同时如果有环的话记录下快慢指针相遇的地方
假设从链表头到环入口距离为a，快慢指针相遇处距入口距离为b，那么慢指针走了a+b，而快指针走了2a+2b，记相遇处绕回到入口处距离为c，那么快指针多走了一圈（假设），即c+b，即a=c，此时让一个指针从链表头开始走c步，一个指针同时在相遇处走c步，那么他们会在入口相遇
实际上如果相遇，快指针比慢指针会多跑k圈（一圈就是b+c），此时慢指针走了a+b，快指针走了2（a+b），就会有2（a+b）=a+b+k（b+c）
可以算出来a=k（b+c）-b，就是a=（k-1）（b+c）+c
此时让一个指针从起点跑a步会到达入口处，一个指针从相遇处跑a步也就是几圈+c步也会到达入口处，此时他们相遇于入口
/*** 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) {ListNode *slow = head, *fast = head;do {if (fast == nullptr || fast->next == nullptr)return nullptr;slow = slow->next;fast = fast->next->next;} while (fast != slow);fast = head;while (fast != slow) {fast = fast->next;slow = slow->next;}return slow;}
};两数相加
2. 两数相加 - 力扣（LeetCode）
同步遍历两个链表，用一个数记录进位，用一个数记录和，链表到空了就当成0继续加起来，直到两个链表都遍历完并且用完进位
/*** 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 head{};ListNode* cur = &head;int carry = 0;while (l1 || l2 || carry) {int a = l1 == nullptr ? 0 : l1->val;int b = l2 == nullptr ? 0 : l2->val;int sum = a + b + carry;cur->next = new ListNode(sum % 10);cur = cur->next;carry = sum / 10;if (l1)l1 = l1->next;if (l2)l2 = l2->next;}return head.next;}
};删除链表的倒数第N个节点
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
链表倒数可以利用递归从最后一个开始往前数，到了该删的那个先记录后驱节点，然后释放本节点
再返回后驱节点接上
还可以用双指针的方法，记链表总个数为L，倒数第N个也就是正数第L-N个，用一个指针先跑到第N个节点，然后让另一个指针从起点开始跑，当前面一个指针跑到末尾时，它跑了L-N个节点，也就是后面一个节点跑了L-N个节点，即倒数第N个节点
/*** 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 {int count = 0;public:ListNode* removeNthFromEnd(ListNode* head, int n) {if (head == nullptr)return head;head->next = removeNthFromEnd(head->next, n);++count;if (count == n) {ListNode* next = head->next;delete head;return next;}return head;}
};两两交换链表中的节点
24. 两两交换链表中的节点 - 力扣（LeetCode）
就先看两个，先取第二个的指针，递归颠倒第二个后面的节点，链接到第一个节点上，然后把第一个节点链接到第二个节点上，返回第二个节点指针
/*** 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* next = head->next;head->next = swapPairs(next->next);next->next = head;return next;}
};随机链表的复制
138. 随机链表的复制 - 力扣（LeetCode）
非常妙的思路，用映射将旧链表的节点和新链表的节点一一对应起来，然后将新链表的节点串起来，对于random可以根据哈希表里面的对应找到新链表里面对应的节点，妙哉
/*
// 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) {unordered_map<Node*, Node*> hash;Node* cur = head;while (cur) {hash[cur] = new Node(cur->val);cur = cur->next;}cur = head;while (cur) {hash[cur]->next = hash[cur->next];hash[cur]->random = hash[cur->random];cur = cur->next;}return hash[head];}
};排序链表
148. 排序链表 - 力扣（LeetCode）
最快的方法是取出来放数组里面排序数组再装回去
原地排序的话可以使用归并排序，用快慢指针找到中间节点拆成两个链表，递归继续拆，拆到只有一个节点的链表，合并两个有序链表
/*** 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* merge(ListNode* l1, ListNode* l2) {if (l1 == nullptr)return l2;if (l2 == nullptr)return l1;if (l1->val < l2->val) {l1->next = merge(l1->next, l2);return l1;}l2->next = merge(l1, l2->next);return l2;}ListNode* findMidst(ListNode* head) {ListNode *slow = head, *fast = head;while (fast->next && fast->next->next) {slow = slow->next;fast = fast->next->next;}return slow;}ListNode* sortList(ListNode* left) {if (left == nullptr || left->next == nullptr)return left;ListNode* midst = findMidst(left);ListNode* right = midst->next;midst->next = nullptr;return merge(sortList(left), sortList(right));}
};N个一体翻转链表
这里的N个是指作为一个整体例如12345，N=2，即将12 34 5进行翻转成5 34 12，并不是K个一组翻转
思路很巧妙，在刚刚代码的基础上，找到需要翻转的整体的开始节点和结束节点
Node *reverseList(Node *head,const int N) {Node *prev = nullptr;Node *curEnd = head;while (curEnd) {int n = N;Node*curBegin=curEnd;while (--n&&curEnd->next) {curEnd=curEnd->next;}Node *next = curEnd->next; // 记录下当前节点的后一个节点curEnd->next = prev; // 核心步骤：前一个节点放到当前节点的后面prev = curBegin;curEnd = next;}return prev;
}K个一组翻转链表
每K个一组里面翻转，先找出每一个组的头，翻转这一个组，然后将这一个组接到当前组的后面
class Solution {
public:ListNode* reverseKGroup(ListNode* cur, int k) {ListNode* newHead = cur;for (int i = 0; i < k; ++i) {if (newHead == nullptr) {return cur;}newHead = newHead->next;}ListNode* prev = reverseKGroup(newHead, k);for (int i = 0; i < k; ++i) {ListNode* next = cur->next;cur->next = prev;prev = cur;cur = next;}return prev;}
};合并两个有序链表
迭代法，先创建一个头节点，然后同步遍历两个链表节点取较小的节点接上去直到某个链表为空，再把不为空的链表接上去
class Solution {
public:ListNode *mergeTwoLists(ListNode *list1, ListNode *list2) {ListNode head{};ListNode *cur = &head;while (list1 && list2) {if (list1->val < list2->val) {cur->next = list1;list1 = list1->next;} else {cur->next = list2;list2 = list2->next;}cur = cur->next;}cur->next = list1 ? list1 : list2;return head.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;}list2->next = mergeTwoLists(list1, list2->next);return list2;}
};合并K个升序链表
23. 合并 K 个升序链表 - 力扣（LeetCode）
方法一：每次取最小的一个节点出来返回，递归取更小的节点作为后驱节点
/*** 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 *mergeKLists(vector<ListNode *> &lists) {int min = INT_MAX, index = -1;for (int i = 0; i < lists.size(); ++i) {if (lists[i] && lists[i]->val < min) {min = lists[i]->val;index = i;}}if (index == -1)return nullptr;ListNode *head = lists[index];lists[index] = lists[index]->next;head->next = mergeKLists(lists);return head;}
};双向链表+哈希表 LRU
哈希查找快，双向链表维护最久不使用的更新
class LRUCache {struct Node {int key, value;Node *prev, *next;};Node *head, *tail;unordered_map<int, Node*> hash;int capacity;void moveToHead(Node* node) {node->prev = head;node->next = head->next;head->next->prev = node;head->next = node;}void removeNode(Node* node) {node->prev->next = node->next;node->next->prev = node->prev;}public:LRUCache(int capacity) {this->capacity = capacity;head = new Node{};tail = new Node{};head->next = tail;tail->prev = head;}int get(int key) {if (hash.find(key) == hash.end()) {return -1;}removeNode(hash[key]);moveToHead(hash[key]);return hash[key]->value;}void put(int key, int value) {if (hash.find(key) == hash.end()) {if (hash.size() == capacity) {Node* node = tail->prev;hash.erase(node->key);removeNode(node);delete node;}hash[key] = new Node{key, value, nullptr, nullptr};} else {hash[key]->value = value;removeNode(hash[key]);}moveToHead(hash[key]);}
};
Main
#include<iostream>
#include<vector>struct Node {int value = 0;Node *next = nullptr;
};
void deleteNode(Node*p) {if(p==nullptr)return;if(p->next==nullptr) {delete p;return;}Node*temp=p->next;p->next=temp->next;p->value=temp->value;delete temp;
}Node *vectorTOList(std::vector<int> nums) {if (nums.empty())return nullptr;Node *head = new Node();head->value = nums[0];Node *cur = head;for (int i = 1; i < nums.size(); ++i) {cur->next = new Node{nums[i], nullptr};cur = cur->next;}return head;
}void showList(Node *head) {if (head == nullptr)return;while (head) {std::cout << head->value << ' ';head = head->next;}std::cout << '\n';
}int main() {std::vector<int> nums = {1, 2, 3, 4, 5};Node *list1 = vectorTOList(nums);showList(list1);showList(reverseList(list1,2));Node *list2 = vectorTOList(nums);showList(list2);showList(reverseList(list2,1));return 0;
}
