目录
🌼相交链表
3 种方法
注意：交叉不是值相等，直接两个结构体指针 == （判等）
第 1 种（哈希）：时间 O(m + n)，空间 O(m)
unordered_set 哈希表，先将 listA 所有元素加入哈希表，用 .count() 查询 listB 中的元素是否在 map 中
第 2 种（双指针）：时间 O(m + n)，空间 O(1)
官解解法二，双指针，特点是，listA，listB 中指针非空时，同时向后移动，直到一方为 nullptr，然后跳到另一个链表头指针位置，继续移动；当双方都跳到对方头部，且再次移动到 nullptr 时，还未 ==，意味着没有交叉点，否则中间必然出现 == 情况，return
第 3 种（截去较长的list）：时间 O(m + n)，空间 O(1)
类似官解二，但是，先找到长度 m, n 较小值，然后让较长的 list 的头指针，先往前移动 m - n 个位置（假设 m > n），然后可以开始同步移动判等 ==
AC 哈希
/**
* 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) {
unordered_set<ListNode *> check_set;
ListNode *temp = headA;
// listA 元素插入哈希表
while (temp != nullptr) {
check_set.insert(temp);
temp = temp->next;
}
// 遍历 listB 判等
temp = headB;
while (temp != nullptr) {
if (check_set.count(temp))
return temp;
temp = temp->next;
}
return nullptr;
}
};AC 双指针
/**
* 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) {
// 特判
if (headA == nullptr || headB == nullptr)
return nullptr;
// 双指针遍历 O(m + n)
ListNode *pA = headA, *pB = headB;
while (pA != pB) { // 直到交叉点 或 同时为空（没有交叉点）
pA = (pA == nullptr ? headB : pA->next);
pB = (pB == nullptr ? headA : pB->next);
}
return pA;
}
};AC 截去较长 list
/**
* 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) {
// 特判
if (headA == nullptr || headB == nullptr)
return nullptr;
// 得到长度
int m = 0, n = 0;
ListNode *temp = headA;
while (temp != nullptr) {
m++;
temp = temp->next;
}
temp = headB;
while (temp != nullptr) {
n++;
temp = temp->next;
}
// 截去较长 list
if (m > n) {
while (m-- != n)
headA = headA->next;
}
else
while (n-- != m)
headB = headB->next;
// 此时长度相等，遍历判等
ListNode *pA = headA, *pB = headB;
while (pA != pB) {
pA = pA->next;
pB = pB->next;
}
return pA;
}
};🌼反转链表
做链表的题，一定要画图，明确 建立新连接 的过程，代码就很容易写了
2 种方法
第 1 种（迭代）
时间 O(n)，空间 O(1)
3 个变量，pre, cur, nex，代表 3 个位置，同步向右移动，有个小坑，二刷时写一遍就知道了
第 2 种（递归）
时间 O(n)，空间 O(n)
先解释下递归👇
遇到递归就模拟栈，顶层的元素被加入栈底，回溯时，栈底最后出栈，栈顶先出栈
关于递归中return的理解（最浅显易懂）_都return了为什么还在递归-CSDN博客
大家可以想像一下，要计算1~100的累加和 sum(100)，假设有一个栈，先将 sum(100) 插入，再插入 sum(99)，直到 sum(1)，此时 sum(100) 在栈底。
n == 1 就是递归的出口，此时从 sum(1) 开始出栈，直到 sum(100) 出栈，得到结果
最顶层是 n1 开始，最顶层 n1 插入栈底，回溯时，先得到 nm 的 return，
这里明确下，递归的出口时，head == nullptr 或 head->next == nullptr，
当到达递归出口时，表示到达了 nm，nm 直接返回，然后开始 n m-1.....
n m-1 在 nm 的基础上 return，同理，先 return 了 n3，才有后续的 n2，return 了 n2 才有 n1
AC 迭代
/**
* 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) {
// 画图辅助理解
// pre, cur, nex 是反转后的相对位置
// cur 当前位置，pre 上一位置，nex 下一位置
ListNode *cur = head, *nex = nullptr;
while (cur != nullptr) {
// pre 声明在 while 里，确保 cur 不为空
ListNode *pre = cur->next; // pre 为 cur 右一位置
// 建立新的连接
cur->next = nex;
// nex, cur 同时右移 1 个位置
nex = cur;
cur = pre;
}
// 此时 cur 指向空，nex 为新的头指针
return nex;
}
};AC 递归
/**
* 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) {
// 链表为空 || 递归出口
if (head == nullptr || head->next == nullptr) {
return head; // m 出栈
}
// 递归调用
// 1 ~ m 入栈
ListNode *newNode = reverseList(head->next); // 新的头节点
// m-1 ~ 1 出栈
head->next->next = head; // next 反向
head->next = nullptr; // 单向链表 且 n1指向nullptr
return newNode; // 返回新的节点
}
};🌼回文链表
3 种方法
第 1 种（数组）：时间 O(n)，空间 O(n)
拷贝到数组，然后双指针
第 2 种（递归）：时间 O(n)，空间 O(n)
递归栈辅助理解：
frontPoiner 从初始的头指针 head 开始，而递归函数中的 curNode 指针，n1 递归到 nm（每次函数执行一半，就要进入下一个递归），才真正开始执行后面的 curNode->val != frontPointer->val 的操作
第 3 种（快慢指针）：时间 O(n)，空间 O(1)
需要写 3 个函数：
a. 给定的判断回文的函数 b. 链表反转（给定指针往后） c. 查找前半部分的尾节点
链表反转，采取 “反转链表” 那题，迭代的方法
查找前半部分尾节点，采取快慢指针，快指针一次走 2 步，慢指针一次 1 步
判断回文，分别从 head 和 后半部分起点 出发
---------------
判断完回文后，最好能恢复链表（后半部分再次反转）
具体链表节点 奇数 / 偶数 的情况，自己模拟下
AC 数组
/**
* 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> arr; // 类型是 int
// 拷贝到数组
while (head) {
arr.push_back(head->val); // 插入的是大小
head = head->next;
}
int n = arr.size();
// 比较回文
for (int i = 0, j = n - 1; i < j; ++i, --j)
if (arr[i] != arr[j])
return false;
return true;
}
};AC 递归
1，题目原文 “给你一个单链表的头节点
head”，所以 head 可以作为函数参数传入函数，但是只能作为函数参数传入，不能在类内直接赋值给其他变量
2，力扣真的🤢，函数名都不让改，还是喜欢 ACM 模式，自己写处理舒服多了，力扣天天各种 BUG，函数 isPalindrome() 是给定的，不能改
3，return true; 或者 return false;
只会退出当前层递归，所以一个 true 无法影响到最终返回值
但只要出现一次 false，考虑到 if (check(curNode->next) == false) return false;
最终返回的就是 false
class Solution {
ListNode *frontPointer;
public:
bool check(ListNode *curNode) {
if (curNode != nullptr) { // 当前节点非空
if (check(curNode->next) == false) // 递归下一节点
return false;
// head 从 nm 开始出栈, n1 在栈底
if (frontPointer->val != curNode->val) // curNode: m ~ 1
return false; // 非回文串
frontPointer = frontPointer->next; // 1 ~ m
}
return true; // 退出当前层递归
}
bool isPalindrome(ListNode *head) {
frontPointer = head;
return check(head);
}
};AC 快慢指针
这里的 “链表反转” 函数，举个例子，
1->2->3->4->4->3->2->1->nullptr 变成了 1->2->3->4->4<-3<-2<-1（而且后半部分终点 4 指向 nullptr）（第一次反转把后半部分开头的 4 传入；第二次反转传入的是最右边的 1，因为反转函数，会返回新的头指针）
class Solution {
public:
// 特判 + 判断回文 + 恢复链表
bool isPalindrome(ListNode* head) {
// 特判 空链表
if (head == nullptr)
return true;
ListNode *endFirst = end_of_first(head); // 前半尾节点
// 反转链表
ListNode *frontSecond = reverseList(endFirst->next); // 后半新的头节点
// 判断回文
ListNode *p1 = head, *p2 = frontSecond;
bool flag = 1;
while (p2 != nullptr && flag) {
if (p1->val != p2->val)
flag = 0;
p1 = p1->next, p2 = p2->next;
}
// 恢复链表 -- 再次反向
endFirst->next = reverseList(frontSecond);
return flag;
}
// 反转链表，传入反转前头指针，返回反转后头指针
ListNode* reverseList(ListNode* head)
{ // 1->2->3->o o<-1<-2<-3
ListNode *nex = nullptr, *cur = head;
while (cur != nullptr) {
ListNode *pre = cur->next; // pre在cur右一位置
cur->next = nex; // 建立新连接
nex = cur; // nex 右移
cur = pre; // cur 右移
}
return nex; // cur 为空时, nex 刚好在新的头节点位置
}
// 传入 头指针，返回 前半部分尾节点
ListNode* end_of_first(ListNode* head)
{
ListNode *fast = head, *slow = head; // 快慢指针
while (fast->next != nullptr && fast->next->next != nullptr) {
fast = fast->next->next; // 一次两步
slow = slow->next;
}
return slow; // 前半部分尾节点
}
};🌼环形链表
1，哈希表 2，快慢指针
快慢指针这个，开始考虑，能否只用一个指针，只需判断 == head，后来发现，head 可能不在环里，所以还是得两个指针
AC 哈希表
时间 O(n)，空间 O(n)
/**
* 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) {
unordered_set<ListNode *>s; // 哈希表
while (head != nullptr) {
if (!s.empty() && s.count(head))
return true;
s.insert(head);
head = head->next;
}
return false;
}
};AC 快慢指针
时间 O(n)，空间 O(1)
/**
* 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) {
ListNode *fast = head;
ListNode *slow = head;
while (fast != nullptr && fast->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) // 不需要判断非空，因为非空的fast不会进去循环
return true;
}
return false;
}
};🚩环形链表 II
1，哈希表：遍历一遍，第一个 s.count() 已存在的，就是交叉点
2，快慢指针👇
x -- head 到交叉点路程
y -- 快慢指针相遇位置
z -- 相遇位置回到交叉点
已知 fast 是 slow 的两倍速度，且 fast 至少转 1 圈（y + z）才能遇到 slow
假设转了 n 圈
fast 走过的路程 = x + y + n*(y + z)
slow 走过的路程 = x + y
可得等式：2*slow = fast
得到 x + y = n*(y + z)，即 x = (n - 1) * (y + z) + z
表示，head 到 交叉点 == 快慢指针相遇点 + n-1 圈
根据上面等式，只需在相遇的同时，头指针从 head 开始移动，俩慢指针相遇点即可 return
AC 哈希表
时间 O(n)，空间 O(n)
/**
* 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) {
unordered_set<ListNode *>s;
while (head != nullptr) {
if (s.count(head))
return head; // 先判断
s.insert(head); // 再插入
head = head->next;
}
return nullptr;
}
};AC 快慢指针
注意：只有一个节点时，没有环，此时 head->next == nullptr
时间 O(n)，空间 O(1)
时间分析：slow 到相遇点，< O(n)；slow 从相遇点到交叉点，也 < O(n)，总共时间 < O(2n)，所以是 O(n)
/**
* 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 *fast = head;
ListNode *slow = head;
while (fast != nullptr) {
slow = slow->next;
if (fast->next == nullptr) // 无环
return nullptr;
fast = fast->next->next;
if (fast == slow) { // 快慢指针相遇点
// 相遇后，说明一定有环，即有交叉点
while (slow != head) {
head = head->next; // 头节点出发
slow = slow->next; // 相遇点出发
}
return slow; // 交叉点
}
}
return nullptr;
}
};🌼合并两个有序链表
题目中 “
l1和l2均按 非递减顺序 排列”，这里的非递减，可以理解为，存在相等的递增序列
1，递归：l1, l2 任一存在空链表，返回另一链表；然后递归取较小值
2，迭代：
AC 递归
时间 O(n + m)，空间 O(n + m)
时间需要递归 n + m 次，空间递归栈的深度 n + m
/**
* 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* 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;
}
else {
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
};AC 迭代
时间 O(n + m)，空间 O(1)
/**
* 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* list1, ListNode* list2) {
ListNode *prev = new ListNode(-1); // 只初始化值的构造函数
ListNode *p = prev; // 哨兵
// 直到一条链遍历完
while (list1 != nullptr && list2 != nullptr) {
if (list1->val < list2->val) {
p->next = list1; // 注意这里是 p->next，下一位置
list1 = list1->next;
}
else {
p->next = list2;
list2 = list2->next;
}
p = p->next;
}
// 将未遍历完的链，接到新的链表后
p->next = (list1 == nullptr) ? list2 : list1;
return prev->next; // 新链表头指针
}
};