总的地址 :
面试经典 150 题 - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台
c++链表总结 :
链表总结 -- 《数据结构》-- c/c++-CSDN博客
141 . 环形链表
详细题解参考 :
141 . 环形链表-CSDN博客
这里给出慢双指针的代码 :
/**
* 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* slow = head;
ListNode* fast = head->next;
while(slow != fast){
if(fast == nullptr || fast->next == nullptr){
return false;
}
slow = slow->next;
fast = fast->next->next;
}
return true;
}
};2 . 两数相加
法1
递归 ， 这里是具有子问题的性质的 , 然后模拟乘法 ;
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
return addTwo(l1, l2, 0);
}
// l1 和 l2 为当前遍历的节点，carry 为进位
private ListNode addTwo(ListNode l1, ListNode l2, int carry) {
if (l1 == null && l2 == null) // 递归边界：l1 和 l2 都是空节点
return carry != 0 ? new ListNode(carry) : null; // 如果进位了，就额外创建一个节点
if (l1 == null) { // 如果 l1 是空的，那么此时 l2 一定不是空节点
l1 = l2;
l2 = null; // 交换 l1 与 l2，保证 l1 非空，从而简化代码
}
carry += l1.val + (l2 != null ? l2.val : 0); // 节点值和进位加在一起
l1.val = carry % 10; // 每个节点保存一个数位
l1.next = addTwo(l1.next, (l2 != null ? l2.next : null), carry / 10); // 进位
return l1;
}
}
法二 :
迭代 ， 模拟这个加法的过程 ;
/**
* 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) {
auto dmy = new ListNode() ;// 哨兵结点
auto cur = dmy ;
ListNode* tmp ;
int cay = 0 ;
while(l1 || l2 || cay){
cay += (l1 ? l1->val : 0) + (l2 ? l2->val : 0) ;
tmp = new ListNode(cay % 10);
cur -> next = tmp ;
cur = cur -> next ;
cay /= 10 ;
if(l1) l1 = l1 -> next ;
if(l2) l2 = l2 -> next ;
}
return dmy -> next ;
}
};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) {
if(l1 == nullptr) return l2;
else if(l2 == nullptr) return l1;
else if(l1->val < l2->val){
l1->next = mergeTwoLists(l1->next,l2);
return l1;
} else {
l2->next = mergeTwoLists(l1,l2->next);
return l2;
}
}
};双指针迭代
/**
* 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* ans = new ListNode(-1);
ListNode* tmp = ans;
while(l1!=nullptr && l2!=nullptr){
if(l1->val <= l2->val){
tmp->next = l1;
l1 = l1->next;
}else {
tmp->next = l2;
l2 = l2->next;
}
tmp = tmp->next;
}
tmp->next = l1==nullptr ? l2 : l1;
return ans->next;
}
};138 . 随机链表的复制
题意
这一题的题意可能难以理解 ;
下面给出在lc评论区的一段话，可能帮助理解 :
题目要求我们给定一个链表，每个节点除了包含一个指向下一个节点的指针（next），还包含一个随机指针（random），该随机指针可以指向链表中的任何节点或空节点。我们需要构造一个深拷贝的链表，使得新链表与原链表具有相同的结构和值，但是新链表中的节点均为全新的节点。
换句话说，我们需要创建一个与原链表结构相同的链表，其中每个节点的值与对应原节点的值相同，并且每个节点的next指针和random指针都指向新链表中对应的节点。
例如，原链表为：A -> B -> C，其中A.random指向C，B.random指向A，C.random指向B。那么深拷贝后的链表为：A' -> B' -> C'，其中A'.random指向C'，B'.random指向A'，C'.random指向B'。
（难点就是创建链表时random指的可能还没创建出来，要解决的就是这个）
思路 :
哈希表
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head == nullptr) return nullptr;
Node* cur = head;
unordered_map<Node*, Node*> map;
// 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
while(cur != nullptr) {
map[cur] = new Node(cur->val);
cur = cur->next;
}
cur = head;
// 4. 构建新链表的 next 和 random 指向
while(cur != nullptr) {
map[cur]->next = map[cur->next];
map[cur]->random = map[cur->random];
cur = cur->next;
}
// 5. 返回新链表的头节点
return map[head];
}
};
92 . 反转链表II
图文题解见 :
反转链表【基础算法精讲 06】-CSDN博客
这一题只需要反转[l,r]的部分结点
将反转链表的前一个结点成为p0 ;
然后和上一题一样反转链表 ;
也就是 :
把p0的next指针指向cur,p0指向pre
有一个特殊的情况，当l = 1 的时候 ， 没有p0 , 可以在前面加上一个哨兵结点为p0 ;
代码如下 :
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode* dmy = new ListNode(0,head) ;
ListNode* p0 = dmy ;
for(int i=0;i<left-1;i++){
p0 = p0 -> next ;
}
ListNode* pre = nullptr ;
ListNode* cur = p0->next ;
for(int i=1;i<=right-left+1;i++){
ListNode* nxt = cur->next ;
cur->next = pre ;
pre = cur ;
cur = nxt ;
}
p0->next->next = cur ;
p0->next = pre ;
return dmy->next ;
}
};25 . k个一组反转链表
和上题类似 ，每逢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:
ListNode* reverseKGroup(ListNode* head, int k) {
int n = 0 ;
ListNode* cur = head ;
while(cur!=nullptr){ // 拿到链表的长度
n++;
cur = cur->next ;
}
ListNode* dmy = new ListNode(0,head) ;
ListNode* p0 = dmy ;
while(n>=k){
n-=k;
ListNode* pre = nullptr;
ListNode* cur = p0->next ;
for(int i=0;i<k;i++){
ListNode* nxt = cur->next;
cur->next = pre ;
pre = cur ;
cur = nxt ;
}
ListNode* tmp = p0->next ;
p0->next->next = cur ;
p0->next = pre ;
p0 = tmp ;
}
return dmy -> next;
}
};19 . 删除链表的倒数第N个结点
快慢双指针!!!
快的先跑n个，然后快慢同时跑，快的跑到终点，慢的也就到了倒数第n+1个的位置!!!
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dmy = new ListNode(0,head) ;
dmy->next = head ;
ListNode* fast = head , *slow = dmy ;
// 快的先跑n个
for(int i=0;i<n;i++) fast = fast -> next ;
// 快的跑 len - n , 慢的也就跑到了倒数第n个
while(fast){
fast = fast -> next ;
slow = slow -> next ;
}
slow -> next = slow -> next -> next ;
ListNode* ans = dmy -> next ;
delete dmy ;
return ans ;
}
};82 . 删除排序链表中的重复元素 II
双指针解决!!!
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null){
return head ;
}
ListNode dummy = new ListNode(0,head) ;
ListNode cur = dummy ;
while(cur.next != null && cur.next.next != null){
if(cur.next.val == cur.next.next.val){
int x = cur.next.val ;
while(cur.next != null && cur.next.val == x){
cur.next = cur.next.next ;
}
}else{
cur = cur.next ;
}
}
return dummy.next ;
}
}61 . 旋转链表
先变成环 ， 再剪开 ;
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (k == 0 || head == nullptr || head->next == nullptr) {
return head;
}
int n = 1;
ListNode* iter = head;
while (iter->next != nullptr) {
iter = iter->next;
n++;
}
int add = n - k % n;
if (add == n) {
return head;
}
iter->next = head;
while (add--) {
iter = iter->next;
}
ListNode* ret = iter->next;
iter->next = nullptr;
return ret;
}
};
86 . 分隔链表
直观来说我们只需维护两个链表 smalll 和 large即可，small链表按顺序存储所有小于 xxx 的节点，large 链表按顺序存储所有大于等于 x 的节点。遍历完原链表后，我们只要将 small 链表尾节点指向 large链表的头节点即能完成对链表的分隔。
代码如下 :
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode* small = new ListNode(0);
ListNode* smallHead = small;
ListNode* large = new ListNode(0);
ListNode* largeHead = large;
while (head != nullptr) {
if (head->val < x) {
small->next = head;
small = small->next;
} else {
large->next = head;
large = large->next;
}
head = head->next;
}
large->next = nullptr;
small->next = largeHead->next;
return smallHead->next;
}
};
146 . LRU缓存
双链表 + 哈希表
struct DLinkedNode {
int key, value;
DLinkedNode* prev;
DLinkedNode* next;
DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};
class LRUCache {
private:
unordered_map<int, DLinkedNode*> cache;
DLinkedNode* head;
DLinkedNode* tail;
int size;
int capacity;
public:
LRUCache(int _capacity): capacity(_capacity), size(0) {
// 使用伪头部和伪尾部节点
head = new DLinkedNode();
tail = new DLinkedNode();
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (!cache.count(key)) {
return -1;
}
// 如果 key 存在，先通过哈希表定位，再移到头部
DLinkedNode* node = cache[key];
moveToHead(node);
return node->value;
}
void put(int key, int value) {
if (!cache.count(key)) {
// 如果 key 不存在，创建一个新的节点
DLinkedNode* node = new DLinkedNode(key, value);
// 添加进哈希表
cache[key] = node;
// 添加至双向链表的头部
addToHead(node);
++size;
if (size > capacity) {
// 如果超出容量，删除双向链表的尾部节点
DLinkedNode* removed = removeTail();
// 删除哈希表中对应的项
cache.erase(removed->key);
// 防止内存泄漏
delete removed;
--size;
}
}
else {
// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
DLinkedNode* node = cache[key];
node->value = value;
moveToHead(node);
}
}
void addToHead(DLinkedNode* node) {
node->prev = head;
node->next = head->next;
head->next->prev = node;
head->next = node;
}
void removeNode(DLinkedNode* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void moveToHead(DLinkedNode* node) {
removeNode(node);
addToHead(node);
}
DLinkedNode* removeTail() {
DLinkedNode* node = tail->prev;
removeNode(node);
return node;
}
};参考 :
代码随想录
链表总结 -- 《数据结构》-- c/c++-CSDN博客
141 . 环形链表-CSDN博客
反转链表【基础算法精讲 06】-CSDN博客
