链表
依照视频的思路，过一段时间再去
leetcode验证
预备知识: 链表基础
#include <iostream>
namespace LinkedList {
struct ListNode {
int val{0}; // 存储元素的数据域
ListNode *next{nullptr}; // 存储下一个节点地址的指针域
// 这部分原题目估计有问题
};
void learn00::testPrint() {
// 尝试测试链表
// 创建五个节点
ListNode a;
ListNode b;
ListNode c;
ListNode d;
ListNode e;
a.val = 10;
b.val = 20;
c.val = 30;
d.val = 40;
e.val = 50;
// 连接节点
a.next = &b;
b.next = &c;
c.next = &d;
d.next = &e;
ListNode *head = &a;
while(head) {
std::cout << head->val << std::endl;
head = head->next;
}
}
} 链表的创建
基本形式：
struct ListNode {
int val; // 存储元素的数据域
ListNode *next; // 存储下一个节点地址的指针域
}; 一些思考
但值得注意的是，如果按照开头的代码处理链表节点的话，next指针域会随机赋给予初值，此时的地址只想会如下图：
由于ListNode是一个结构体，在C++中与class是基本上无异的。ListNode *next是一个指向ListNode类型的指针，那么编译器将会对next初始化，而我们没有定义初始化的变量是什么，就可能会赋值到随机指针，造成了上述的问题。但具体的变化流程是怎么样的呢？我们再尝试下：
int main() {
ListNode a; // 单独创建一个节点
return 0;
} 它产生的结果：
十分奇怪！那改成一个ListNode *a。
这样也懵了，两者为何不相同呢？
我们一步一步来分析:
ListNode a; // 0 此时a 是一个 ListNode类型的变量 // 1 而a中有一个 ListNode 的指针 next // 2 我们在初始化a时没有赋予其一个规定的初值 因而 next也会初始化自己 // 3 因而 next 是指向一个ListNode的 指针，编译器需要找一个ListNode类型的值，并找到它的地址 // 4 实际上我们并没有手动创造这么一样定义，于是编译器会去尝试去初始化next // 5 而next的指向的地址依旧需要一个 next 指针，编译器会再尝试去初始化 ListNode *a; // 按照上述分析，而我们对比，可以看到指针的ListNode初始化的层数比上述的少一层
再者，先推断，编译器会尝试初始化两层指针(next)。我们整个ListNode **a：
编译器很无力。
而前面我们还注意到一些问题，在声明多个变量的时候，出了些问题，第一个变量默认值为0，地址也为nullptr：
ListNode a; ListNode b; ListNode c;
很明显，这个情况不可复现！
没有找到相关的资料，这也是奇怪的现象。可能是C++编译器的问题，于是乎我尝试写了下C的版本，得到下面的结果：
很明显，struct结构体的定义就是错误的，如果没有给予编译器明确的指令，明显会出问题！定义链表时，未定义的行为可能是程序崩溃的重要原因。要注意并杜绝这类的行为（主要视频中给出的是这么简陋的定义，尝试分析了下），因而正常应当在结构体中赋予变量初值，next指向nullptr（这也是链表在书面上的定义与要求）。
C中还需要写一个函数进行初始化操作:
void InitListNode(ListNode * List) {
List->val = 0;
List->next = NULL;
}
// 那编译器自动创建的地址怎么办？ C++中struct就是class（细节上有区别），可以直接实现初始化：
struct ListNode {
int val{0}; // 存储元素的数据域
ListNode *next{nullptr}; // 存储下一个节点地址的指针域
// 这部分原题目估计有问题
}; 一般的，初始化在构造函数中实现：
struct ListNode {
int val; // 存储元素的数据域
ListNode *next; // 存储下一个节点地址的指针域
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
// 这部分原题目估计有问题
}; 
链表的逆置
基本思路已经写入代码注释
v1. 直接反转链表
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
/**
依次遍历链表节点，每遍历一个节点即逆指一个节点
1. 备份 head->next
2. 修改 head->next
3. 移动 head 与 new_head
*/
ListNode* reverseList(ListNode* head) {
ListNode* new_head = nullptr;
ListNode* tmp = head;
while (tmp) {
// 1. 备份 head->next
ListNode* next = tmp->next;
// 2. 修改 head->next
tmp->next = new_head;
// 3. 移动 head 与 new_head
new_head = tmp;
tmp = next;
}
return new_head;
}
}; v2. 反转从m到n的链表
输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL
// 链表 从 m 逆置到 n
ListNode* reverseBetween(ListNode *head, int m, int n) {
// 1. 计算需要逆置的节点个数
int chang_len = n - m + 1;
// 2. 初始化开始逆置节点的前驱
ListNode *pre_head = nullptr;
// 3. 最终转换后的链表头节点，非特殊情况即为head
ListNode *result = head;
while (head && --m) {
// 4. 将 head 向前移动 m-1 个位置
// 记录head的前驱
pre_head = head;
head = head->next;
}
// 5. 将 modify_list_tail 指向当前的 head，即逆置后的链表尾
ListNode *modify_list_tail = head;
ListNode *new_head = nullptr;
// 6逆置 change_len 个节点
while (head && chang_len) {
// 同 链表逆置1的方法
ListNode *next = head->next;
head->next = new_head;
new_head = head;
head = next;
// 完成一个节点逆置
--chang_len;
}
// 7 连接 尾节点
// 连接逆置后链表尾与逆置段的后一个节点
modify_list_tail->next = head;
// 8 如果 pre_head不空，说明不是从第一个节点开始逆置的 m>1
// 连接头节点
if (pre_head) {
// 不是第一个节点逆置
pre_head->next = new_head;
} else {
// 直接赋值
// 如果pre_head 为空 说明 m==1 从第一个节点开始逆置 结果为逆置后的头节点
result = new_head;
}
return result;
} 求两个链表的交点
法1: set的使用
ListNode* getIntersectionNode(ListNode *headA, ListNode *headB) {
std::set<ListNode *> node_set;
// 1. 遍历遍表A
while(headA) {
node_set.insert(headA);
headA = headA->next;
}
// 2. 在b中查找该节点
while(headB) {
if (node_set.find(headB) != node_set.end()) {
return headB;
}
headB = headB->next;
}
return nullptr;
} set 查找的时间复杂度 O(nlogn)，而查找 headB 最差时间复杂度是 O(n) 。空间复杂度 O(n) 。不符合题意。
法2: 先同步链表再查找
// 获取链表长度 O(n)
int get_list_length(ListNode* head) {
int len{0};
while (head) {
++len;
head = head->next;
}
return len;
}
// 同步 O(m-n)
ListNode * forward_long_list(int long_len, int short_len, ListNode *head) {
// 同步
int delta{long_len - short_len};
while (head && delta) {
head = head->next;
--delta;
}
return head;
}
// 时间 O(n)
// 空间 O(1)
ListNode * getIntersectionNode(ListNode *headA, ListNode *headB) {
int list_A_len = get_list_length(headA);
int list_B_len = get_list_length(headB);
if (list_A_len > list_B_len) {
headA = forward_long_list(list_A_len, list_B_len, headA);
} else {
headB = forward_long_list(list_B_len, list_A_len, headB);
}
// 遍历两个链表
while (headA && headB) {
if (headA == headB) {
return headA;
}
headA = headA->next;
headB = headB->next;
}
return nullptr;
} 此时明显空间复杂度在 O(1) ，而时间复杂度 为 O(n) 。
链表求环
法1: 利用set
- 遍历链表，将链表中的节点对应的地址插入
set中； - 在遍历时插入节点前，在
set中查找， 第一个在set中发现的节点地址，即是链表的起点
// 时间复杂度 O(n) 空间复杂度 O(n)
ListNode *detectCycle(ListNode *head) {
std::set<ListNode *> node_set;
while (head) {
// 查找是否曾经存入节点
if (node_set.find(head) != node_set.end()) {
return head;
}
node_set.insert(head);
head = head->next;
}
return nullptr;
} 法2: 快慢指针赛跑
设两个指针，一个快指针fast，一个慢指针slow
- -
1 => 2 => 3(环节点) => 4 => 5 => 6 => 3(环节点)
- *slow: 2 ; *fast: 2 3
- *slow: 2 3 ; *fast: 2 3 4 5
- *slow: 2 3 4 ; *fast: 2 3 4 5 6 3
- *slow: 2 3 4 5 ; *fast: 2 3 4 5 6 3 4 5;
依照上述过程，fast 总会和 slow 相遇，而此时我们没有完成查找，只是确定了该链表有环，接下来需要对这个过程分析：
- *fast 遍历过的节点总是 *slow 遍历的节点的两倍；
- 当两者相遇的时候，必定经历了环节点的起始节点；
- 定义： a: 1 2 3; b: 4 5; c: 6
- 则 fast = a + b + c + b, slow = a + b
- a + b + c = 2(a + b)
- 则 a = c; 从而可以推断*head到环起始节点 和 相遇节点到环起始节点相差的节点数一样
- 定义该相遇节点下一个节点为 *meet，接下来移动 *head:
- *meet: 5 ; *head: 1
- *meet: 6 ; *head: 2
- *meet: 3 ; *head: 3
代码实现：
ListNode *detectCycle(ListNode *head) {
// 快指针
ListNode *fast = head;
// 慢指针
ListNode *slow = head;
// 相遇节点
ListNode *meet = nullptr;
// 移动节点
while (fast) {
// 同时走一步
fast = fast->next;
slow = slow->next;
// fast 是 nullptr 弹出
if (!fast) {
break;
}
// fast 快一步
fast = fast->next;
// 如果 fast == slow
if (fast == slow) {
meet = fast;
break;
}
}
// 获得 meet 节点
// 如果 meet nullptr 则不成为环
if (!meet) {
return nullptr;
}
// 此时 包含meet节点
while (head && meet) {
if (head == meet) {
return head;
}
head = head->next;
meet = meet->next;
}
// 空
return nullptr;
} 链表划分
- 建立两个临时节点，一个 *less_head，一个 *more_head;
- 遍历链表，当遇到 < 时 存入 *less_head ; 当遇到 >= 时 存入 *more_head;
- *less_head -> ... -> *more_head -> ... -> *nullptr 完成连接
ListNode* partition(ListNode* head, int x) {
// 两个临时头节点
ListNode less_head(0);
ListNode more_head(0);
ListNode *less_ptr = &less_head;
ListNode *more_ptr = &more_head;
while (head) {
// 如果节点小于x，则将节点插入less_ptr中
if (head->val < x) {
less_ptr->next = head;
less_ptr = head;
} else {
// 如果节点大于等于x，则存入more_ptr中
more_ptr->next = head;
more_ptr = head;
}
// 继续遍历
head = head->next;
}
// 将 less 连接到尾部 more_head 头部
less_ptr->next = more_head.next;
// more 接 nullptr
more_ptr->next = nullptr;
// 已经存储头节点
return less_head.next;
} 时间复杂度O(n)
复杂的链表的深度拷贝
该题目的难点在于如何记录 random 指向的节点，如果记录了 random 指向的节点，就可以照常实现链表的深度拷贝。
预备的知识：map
使用 map 可以存储节点地址与节点序号对应。
#include <iostream>
#include <map>
using namespace std;
class Node {
public:
int label;
Node *next, *random;
Node(int x): label(x), next(nullptr), random(nullptr){}
};
int main()
{
// 设置一个节点map, key 为 节点的地址 , value 为整型 --> 唯一 id 值
std::map<Node *, int> node_map;
Node a(5), b(3), c(6);
a.next = &b;
b.next = &c;
a.random = &c;
b.random = &a;
c.random = &c;
node_map[&a] = 1;
node_map[&b] = 2;
node_map[&c] = 3;
cout << "a.random id = " << node_map[a.random] << endl;
cout << "b.random id = " << node_map[b.random] << endl;
cout << "c.random id = " << node_map[c.random] << endl;
return 0;
} 使用 map 解决该问题
使用两个 map，对于旧链表，存储其节点地址并标注序号；对于新链表，存储其序号并标注其节点地址：
Node* copyRandomList(Node* head) {
if (!head) {
return head;
}
// 地址到节点位置的map
std::unordered_map<Node*, int> old_nodes;
// 使用 vector 根据存储节点位置访问地址
// 也可以使用 map unordered_map<int, Node*>
// vector 可以直接使用push_back替代该功能
std::vector<Node *> new_nodes;
Node * ptr = head;
int index{0};
// 遍历原始列表
while (ptr) {
// 将新链表的节点push入new_nodes中
new_nodes.push_back(new Node(ptr->val));
old_nodes[ptr] = index;
ptr = ptr->next;
++index;
}
// 保证最后一个节点 后续无需多加判断
new_nodes.push_back(nullptr);
ptr = head;
index = 0;
// 再次遍历 写入
while (ptr) {
new_nodes[index]->next = new_nodes[index + 1];
if (ptr->random) {
// 找到 random 的地址对应的id
int id = old_nodes[ptr->random];
// 拷贝对应的 id 指向
new_nodes[index]->random = new_nodes[id];
}
ptr = ptr->next;
++index;
}
return new_nodes[0];
} 时间复杂度 O(n) ，使用 两个 map 存储了数据，空间复杂度 O(n) 。
排序链表的合并
v1: 两个排序链表的合并
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 设置临时头节点
ListNode temp_head(0);
// 使用 pre 指针指向 temp_head
ListNode *pre = &temp_head;
while (l1 && l2) {
// 获取较小的部分
if (l1->val < l2->val) {
// pre->next 指向小的部分
pre->next = l1;
// 往下遍历
l1 = l1->next;
} else {
pre->next = l2;
l2 = l2->next;
}
// 移动指针
pre = pre->next;
}
// 其中一个链表剩余则接下来的节点都是有序的
if (l1) {
pre->next = l1;
}
if (l2) {
pre->next = l2;
}
// temp_head 所在的地址的 next 指向头节点
return temp_head.next;
} 时间复杂度 O(min(m, n)) , m n 分别是 l1 l2 的长度。
v2. 多个排序链表的合并
法1: 暴力合并
参考两个链表的合并，遍历 k 个链表，依次按照两个链表连接的方法连接。连接一个之后存储一个结果中，供下一个连接过程使用。
法2: 排序后遍历
所有节点存入 vector 中，再将 vector 排序，再将节点顺序相连。
时间复杂度 O(kN*logkN) 。
// 排序
static bool cmp(const ListNode *a, const ListNode *b) {
return a->val < b->val;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
// 排序法
std::vector<ListNode *> node_vec;
for (auto *node : lists) {
ListNode *tmp = node;
while (tmp) {
node_vec.push_back(tmp);
tmp = tmp->next;
}
}
// 如果没有链表
if (0 == node_vec.size()) {
return nullptr;
}
// 根据节点的值执行排序
std::sort(node_vec.begin(), node_vec.end(), cmp);
// 连接
for (int i{0}; i<node_vec.size()-1; ++i) {
node_vec[i]->next = node_vec[i+1];
}
node_vec[node_vec.size()-1]->next = nullptr;
return node_vec[0];
} 法3: 分治后相连
对 k 个链表进行分治，两两进行合并。
时间复杂度 O(kNlogk)。
ListNode* mergeKLists(vector<ListNode*>& lists) {
// 分治
if (0 == lists.size()) {
return nullptr;
}
if (1 == lists.size()) {
return lists[0];
}
if (2 == lists.size()) {
return mergeTwoLists(lists[0], lists[1]);
}
// 开始分治
int mid = lists.size() / 2;
std::vector<ListNode *> sub1_lists;
std::vector<ListNode *> sub2_lists;
for (int i{0}; i < mid; ++i) {
sub1_lists.push_back(lists[i]);
}
for (int i{mid}; i < lists.size(); ++i) {
sub2_lists.push_back(lists[i]);
}
ListNode *l1 = mergeKLists(sub1_lists);
ListNode *l2 = mergeKLists(sub2_lists);
return mergeTwoLists(l1, l2);
} 相对排序法，实际运行时间更长（可能机器有优化）。
总结
链表中单链是最简单的，在这么多的题目当中，也是单链的题目最多，而环链为辅助，基本不存在双向链表的题目。
设计链表当中为了提高增删效率，可以自己设计一个双向链表。
链表的头
在数据结构的学习当中，可以清晰的认识到链表的头指针为空（非需要的数据）操作的时候会相当方便，在操作实用数据中，置换头节点不需要考虑特殊情况，只需按照设计好的方法直接执行即可等等。
题目中多数头节点非空，我们可以自己手动第一这个空头节点，方便后面的操作：
ListNode p_head(-1); p_head.next = head; ListNode *pre = &p_head; // 此时 pre->next 指向 head
双指针
链表题目当中，比较普遍的解法是使用 双指针法，也可以当成是多指针法。
首先普通的双指针法，可能是预留当前指针的前一个节点，在删除当前节点时候十分有效，需要分析需求确定是否需要前置节点。
其次是快慢指针，中等难度的题目基本上可以用得上快慢指针，最常见的是可以确定单链的中部：
fast = fast->next->next; slow = slow->next; // fast 永远走两步， slow 走一步 // 当 fast 走到中点的时候，slow刚刚好就在中间
有效的组合应用多指针，可以解决不少问题，慢指针负责记忆，而快指针负责向前探索，想想就效率高。
队列与栈的结合
队列和栈可以独立成一个板块，但 C++ 标准库内置这些数据结构，我们可以借助两者的特性解决链表的问题，如链表的逆置、判断回文等等。
如何组合还是要实质分析，解答完全可以尝试使用其他数据结构的特性实现的。当然，如果能够直接解答，肯定是直接解答分高。
综合方法
难度较大的题目会综合多种方法，而有时候也会出现一些数据结构之外的题目，可能也会有数学相关的问题，不过不难，都可以理解。
链表类的题目都好理解，如果出现了无法理解的题目，那肯定是出题的人不会组织语言，不做的就完事了，这两天碰到几道题目，测试的时候答案都是错误的，但提交能够通过，而且题意和测试用例根本对不上。
做几道质量高的题目并搞懂就过关了，傻乎乎做完全部题目，现在这个情况不太显示。
京公网安备 11010502036488号