链表
依照视频的思路,过一段时间再去
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++
标准库内置这些数据结构,我们可以借助两者的特性解决链表的问题,如链表的逆置、判断回文等等。
如何组合还是要实质分析,解答完全可以尝试使用其他数据结构的特性实现的。当然,如果能够直接解答,肯定是直接解答分高。
综合方法
难度较大的题目会综合多种方法,而有时候也会出现一些数据结构之外的题目,可能也会有数学相关的问题,不过不难,都可以理解。
链表类的题目都好理解,如果出现了无法理解的题目,那肯定是出题的人不会组织语言,不做的就完事了,这两天碰到几道题目,测试的时候答案都是错误的,但提交能够通过,而且题意和测试用例根本对不上。
做几道质量高的题目并搞懂就过关了,傻乎乎做完全部题目,现在这个情况不太显示。