链表
2021/7/17 6:06:42
本文主要是介绍链表，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
目录- JO3 从尾到头打印链表（链表+栈）
- L2 两数相加（字节常考）
- JS18 删除链表的节点（链表+前后双指针）
- JO56 删除链表中重复的结点（有序链表+哨兵节点+双指针）
- JS22 JO14链表中倒数第 k 个节点（链表+快慢指针）
- JS24 JO15反转链表（!!!!!，头插法）
- L92反转部分链表（链表+哨兵结点）
- L25 K个一组翻转链表（字节常考!!!!!链表+哨兵结点）
- JS25 JO16 L21合并两个排序的链表（链表+分治+哨兵结点）
- JS52 JO36两个链表的第一个公共节点（链表+双指针）
- JO25 复杂链表的复制（待写）
- L141 环形链表I
- L142 JO55 环形链表II：链表中环的入口结点（链表+哈希表/快慢指针）
参考
链表：
链表编程边界case检查：
-
如果链表为空时，代码是否能正常工作？
-
如果链表只包含一个结点时，代码是否能正常工作？
-
如果链表只包含两个结点时，代码是否能正常工作？
-
代码逻辑在处理头结点和尾结点的时候，代码是否能正常工作？
哨兵结点dummy node:
-
是虚拟出来的一个节点，不保存数据。
-
哨兵结点的next指针指向链表中的第一个节点。
-
对于哨兵结点，数据域可以不存储任何信息，也可存储如链表长度等附加信息。
-
哨兵结点不是链表所必需的。
头指针:
-
是指向第一个结点的指针。
-
如果链表没有引入哨兵结点，那么头指针指向的是链表的第一个结点。
-
如果有哨兵结点，头指针就指向哨兵结点。
-
-
头指针是链表所必需的。
哨兵结点解决什么问题：
（1）进行链表的删除、插入操作时，对第一个结点的操作更方便
-
如果链表没有哨兵结点，那么头指针指向的是链表的第一个结点，当在第一个结点前插入一个节点时，那么头指针要相应指向新插入的结点，把第一个结点删除时，头指针的指向也要更新。也就是说如果没有哨兵结点，我们需要维护着头指针的指向更新，因为头指针指向的是链表的第一个结点。（第一个节点变化，头指针也变化）
-
如果引入哨兵结点的话，那么哨兵结点的next始终都是链表的第一个结点。（哨兵结点保持不变，头指针也不变，只是哨兵结点的next指针变化）
（2）统一空表和非空表的处理
- 有了哨兵结点之后头指针指向哨兵结点，不论链表是否为空，头指针总是非空，而且哨兵结点的设置使得对链表的第一个位置上的操作与在表中其它位置上的操作一致，即统一空表和非空表的处理。
总结：
-
dummy node是在头结点可能有变化时使用
-
dummy node是链表问题中一个重要的技巧，中文翻译叫“哑节点”，使用通常针对单链表没有前向指针的问题，保证链表的 head不会在删除操作中丢失，
-
当链表的 head 有可能变化（被修改或者被删除）时，使用 dummy node 可以很好的简化代码，最终返回 dummy.next 即新的链表。
链表结构
// 详细版
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) {}
};
// 简单版
struct ListNode{
int val;
ListNode *next;
ListNode(): val(0), next(nullptr){}
};
遍历链表
#include<iostream>
using namespace std;
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:
};
int main(){
// 生成各个节点并连接
ListNode a(10);
ListNode b(20);
ListNode c(30);
ListNode d(40);
ListNode e(50);
a.next = &b;
b.next = &c;
c.next = &d;
d.next = &e;
e.next = nullptr;
// 生成头节点
ListNode *head = &a;
// 遍历方法1：while循环
while(head){
cout<< head->val << endl;
head = head->next;
}
/*
// 遍历方法2：for循环
for (ListNode* p = head; p != null; p = p->next) {
// 迭代访问 p->val
}
*/
return 0;
};
在函数一开始就经常要写的边界条件
if (!head || !head->next) return head; // 空节点或者只有一个节点
函数参数：一般输入链表头结点，返回头结点
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
}
哨兵结点的使用（在链表的题目中，十道有九道会用到哨兵节点）
ListNode* dummy = new ListNode(); dummy->next = head; ListNode* pre = dummy; // 指向当前组的前一个节点 ListNode new_node(0); ListNode* tmp = &new_node;
JO3 从尾到头打印链表（链表+栈）
- 使用
库中的reverse函数
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
if(head == nullptr) return vector<int> ();
vector<int> result;
while(head){
result.push_back(head->val);
head = head -> next;
}
reverse(result.begin(), result.end());
return result;
}
};
- 方法2：使用栈
class Solution {
public:
// 从尾到头问题，可以尝试用栈解决
// 有三种思路
// 思路1：利用栈先入后出的特性完成
// 思路2：存下来然后进行数组翻转
// 思路3：利用递归
vector<int> reversePrint(ListNode* head) {
vector<int> result;
stack<int> stk;
while(head){
stk.push(head->val);
head = head -> next;
}
while(!stk.empty()){
result.push_back(stk.top());
stk.pop();
}
return result;
}
};
L2 两数相加（字节常考）
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
// 保存进位
int tmp = 0;
ListNode *l3 = new ListNode(0); // 哨兵结点
ListNode *p = l3;
// 节点有值或有进位都可以继续相加
while(l1 != nullptr || l2 !=nullptr || tmp !=0)
{
// 取两个加数
int l1val = l1 !=nullptr ? l1->val : 0;
int l2val = l2 !=nullptr ? l2->val : 0;
// 与进位相加
int sumVal = l1val + l2val + tmp;
// 根据当前和结果得到下一位的进位，大于10有进位，小于10没有进位
tmp = sumVal / 10; // 取除数
// 根据当前和结果得到和节点值
p->next = new ListNode(sumVal % 10); // 取余数
// 更新指针
p = p->next;
if (l1 != nullptr)
l1 = l1->next;
if (l2 != nullptr)
l2 = l2->next;
}
return l3->next;
}
};
JS18 删除链表的节点（链表+前后双指针）
class Solution {
public:
// 给定单向链表的头指针和一个要删除的节点的值，删除该节点
// 使用双指针,一个遍历指针，一个遍历指针的前一个指针
ListNode* deleteNode(ListNode* head, int val) {
// 如果要删除的是头结点，单独处理
if(head->val == val) return head->next;
// 两个游标，一个定位删除节点的前一个节点，一个定位删除节点
ListNode *pre = head, *cur = head->next;
// 遍历链表找到要删除的结点
while(cur != nullptr && cur->val!=val){
pre = cur;
cur = cur->next;
}
// 找到要删除的节点后，将前后节点拼接
if(cur != nullptr) pre->next = cur->next;
return head;
}
};
JO56 删除链表中重复的结点（有序链表+哨兵节点+双指针）
- 不保留重复点： 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :val(x), next(NULL) {}
};
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead) {
if(pHead == nullptr || pHead->next == nullptr) return pHead;
// 建立哨兵结点
ListNode* dummy = new ListNode(0);
dummy->next = pHead;
// 设立两个游标： pre和cur指针，pre指针指向当前确定不重复的那个节点，而cur指针相当于工作指针，一直往后面搜索。
ListNode* pre = dummy;
ListNode* cur = dummy->next; // cur是真正工作的指针
while(cur){
// 找到重复的起始节点
if(cur->next != nullptr && cur->val == cur->next->val){
// 通过循环从重复的起始节点开始找到重复的倒数第一个节点（方便拼接）
while(cur->next !=nullptr && cur->val == cur->next->val){
cur = cur->next;
}
// 找到倒一重复节点后，将前面不重复节点与倒一重复节点后面的节点拼接
pre->next = cur->next;
cur = cur->next; // cur从倒一节点后面的节点重新出发
}
// 当前节点不是重复节点
else{
pre = pre->next;
cur = cur->next;
}
}
return dummy->next;
}
};
- 变种：删除链表中的重复结点，保留一个重复点。例如，链表1->2->3->3->4->4->5 处理后为 1->2->3->4->5
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead) {
if(pHead == nullptr || pHead->next == nullptr) return pHead;
// 建立哨兵结点
ListNode* dummy = new ListNode(0);
dummy->next = pHead;
// 设立两个游标： pre和cur指针，pre指针指向当前确定不重复的那个节点，而cur指针相当于工作指针，一直往后面搜索。
ListNode* pre = dummy;
ListNode* cur = dummy->next; // cur是真正工作的指针
while(cur){
// 找到重复的起始节点
if(cur->next != nullptr && cur->val == cur->next->val){
// 通过循环从重复的起始节点开始找到重复的倒数第一个节点（方便拼接）
while(cur->next !=nullptr && cur->val == cur->next->val){
cur = cur->next;
}
// 找到倒一重复节点后，将前面不重复节点与倒一重复节点拼接
pre->next = cur;
// 更新游标
pre = pre->next;
cur = cur->next; // cur从倒一节点后面的节点重新出发
}
// 当前节点不是重复节点
else{
pre = pre->next;
cur = cur->next;
}
}
return dummy->next;
}
};
JS22 JO14链表中倒数第 k 个节点（链表+快慢指针）
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
// 两种思路
// 思路1：利用快慢指针
// 思路2：利用辅助栈
// 这里用快慢指针:让快指针先走k步，然后快、慢指针开始同速前进
// 当快指针走到链表末尾null时，慢指针所在的位置就是倒数第k个链表节点
ListNode* slow = head;
ListNode* fast = head;
while(k--){
fast = fast->next;
}
while(fast){
fast = fast->next;
slow = slow->next;
}
return slow;
}
};
JS24 JO15反转链表（!!!!!，头插法）
class Solution {
public:
// 使用头插法
// 三个指针：一个指向旧链表的头结点，一个指向当前要反转的节点head，一个指向新链表的头节点
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) return head; // 空节点或者只有一个节点
// head为工作指针
// new_head为新链表头结点指针
ListNode* new_head = nullptr;
// old_head为旧链表头结点指针
ListNode* old_head = head;
while(head){
old_head = old_head->next; // 旧链表头节点重新指向
head->next = new_head; // 当前遍历节点指向新链表头节点
new_head = head; // 新链表头节点重新指向
head = old_head; // 更新当前节点
}
return new_head;
}
};
L92反转部分链表（链表+哨兵结点）
反转从位置 left 到 right 的链表。请使用一趟扫描完成反转。
- 方法1：有哨兵结点
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
// 哨兵结点：因为头结点可能变化
ListNode *dummy = new ListNode(0);
dummy->next = head;
// pre用于寻找待反转节点的前一个节点
ListNode *pre = dummy;
// 找到待反转节点的前一个节点
for (int i=1; i<left; ++i) // 题目称位置0元素为第1个节点。如m=1即第1个节点为反转起点，则无需循环
pre=pre->next;
// 待反转起点
ListNode *curr = pre->next; // 当前工作指针
ListNode *old_head = pre->next; // 旧反转链表头
ListNode *new_head = nullptr; // 新已反转链表头
// 开始反转
for (int i = left; i<right+1; ++i) // 从第m开始到n，因为n+1停止
{
old_head = old_head->next; // 旧头重新指向
curr->next = new_head; // 当前反转节点连接新链表
new_head = curr; // 新头重新指向
curr = old_head; // 更新工作指针
}
// 将初始反转起点的next指向curr
pre->next->next = curr;
// 将反转起点的前一个节点指向反转链表的头结点
pre->next = new_head;
return dummy->next;
}
};
- 方法2：无哨兵结点
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
if(!head || !head->next) return head; // 链表没有节点或只有一个节点
int length = right-left+1; // 待反转部分链表的长度
ListNode* pre_head = nullptr; // 待反转部分链表的前一个节点
ListNode* old_head = head; // 待反转链表的头节点（旧部分链表）
ListNode* new_head = nullptr; // 反转链表反转后的头节点（新部分链表）
// 先找到开始反转的节点
while(--left){
pre_head = old_head;
old_head = old_head->next;
}
ListNode* tmp = old_head; // 工作指针，指向待反转的节点
// 开始反转
while(length--){
old_head = old_head->next;
tmp->next = new_head;
new_head = tmp;
tmp = old_head;
}
// 将反转后的部分链表与原链表的前后部分连接起来
if(pre_head){ // 不是从头节点开始反转
pre_head->next->next = old_head;
pre_head->next = new_head;
}
else{ // 从头节点开始反转
head->next = old_head;
head = new_head; // 整个链表头节点发生改变
}
return head;
}
};
L25 K个一组翻转链表（字节常考!!!!!链表+哨兵结点）
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
// 先算链表长度
// 然后将链表长度/k 得到翻转的组数
// 再分别对每一组进行翻转
// 先创建一个临时头节点（因为原来的头节点要变）
ListNode* dummy = new ListNode();
dummy->next = head;
// 计算链表长度
int len = 0;
while(head){
len++;
head = head->next;
}
if(len<k) return dummy->next; // 链表长度小于分组长度时，无需反转
ListNode* pre = dummy; // 指向当前组的前一个节点
ListNode* old_head = dummy->next;
head = dummy->next;
// 遍历每一组
for(int i=0; i<len/k; ++i){
// 对该组节点翻转
ListNode* new_head = nullptr; // 新链表头结点
for(int j=0; j<k; ++j){
old_head = old_head->next;
head->next = new_head; // head为工作指针
new_head = head;
head = old_head;
}
pre->next->next = old_head; // 将该组初始反转节点即反转后末节点连接到下一个组的第一个节点
ListNode* tmp = pre->next; // 临时记录反转后末节点
pre->next = new_head; // 将当前组的前一个节点指向反转后头结点
pre = tmp; // 更新为反转后末节点：反转前第一个节点，下一个组的前一个节点
}
return dummy->next;
}
};
JS25 JO16 L21合并两个排序的链表（链表+分治+哨兵结点）
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 返回的是一个全新的链表，所以创建哨兵结点（临时头节点）
ListNode* dummy = new ListNode(0);
// 创建该全新链表的游标指针
ListNode* tmp = dummy;
// l1和l2分别为两个待排序链表的游标指针
while(l1 && l2){
if(l1->val < l2->val){
tmp->next = l1;
l1 = l1->next;
}
else{
tmp->next = l2;
l2 = l2->next;
}
tmp = tmp->next; // 记得更新新链表当前节点
}
if(l1){ // 如果l1有剩余，接到tmp后
tmp->next = l1;
}
if(l2){ // 如果l2有剩余，接到tmp后
tmp->next = l2;
}
return dummy->next;
}
};
JS52 JO36两个链表的第一个公共节点（链表+双指针）
class Solution {
public:
// A和B同时从自身链表出发，遍历完自己的就遍历对方的，A到B的共同节点和B到A的共同节点所花费的步数是一样的
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* A = headA;
ListNode* B = headB;
while(A != B){
A = A != nullptr ? A->next:headB;
B = B != nullptr ? B->next:headA;
}
return A;
}
};
JO25 复杂链表的复制（待写）
L141 环形链表I
class Solution {
public:
bool hasCycle(ListNode *head) {
// 环形链表一般用快慢指针解决
// 慢指针slow每次走一步
// 快指针fast每次走两步
// 这样，如果链表有环，则它们必定在环内相遇（这是一个定理）
ListNode* slow = head;
ListNode* fast = head;
while(fast && fast->next){ // 如果链表没有结点或者有尾结点（指向NULL），则链表肯定没有环，从而跳出循环
// 慢指针走一步
slow = slow->next;
// 快指针走两步
fast = fast->next->next;
// 如果存在环，则快慢指针必然相遇
if(slow == fast){
return true;
}
}
// 链表没有环
return false;
}
};
L142 JO55 环形链表II：链表中环的入口结点（链表+哈希表/快慢指针）
- 方法1：哈希表
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(head == nullptr || head->next == nullptr) return nullptr;
unordered_map<ListNode*, int> unmp;
while(head){
unmp[head]++;
if(unmp[head] == 2) return head;
head = head->next;
}
/*
while(head){
if(unmp.find(head) != unmp.end()) return head;
unmp[head]++;
head = head->next;
}
*/
return nullptr;
}
};
- 方法2：快慢指针
//先说个定理：两个指针一个fast、一个slow同时从一个链表的头部出发
//fast一次走2步，slow一次走一步，如果该链表有环，两个指针必然在环内相遇
//此时只需要把其中的一个指针重新指向链表头部，另一个不变（还在环内），
//这次两个指针一次走一步，相遇的地方就是入口节点。
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(head == nullptr || head->next == nullptr) return nullptr;
ListNode* slow = head;
ListNode* fast = head;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
if(slow == fast) break;
}
// 当快指针只是到达链尾退出循环时
if(fast == nullptr || fast->next == nullptr) return nullptr;
slow = head;
while(fast != slow){
fast = fast->next;
slow = slow->next;
}
return fast;
}
};
这篇关于链表的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-06-26结对编程到底难不难？答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图，怎么办？
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗？
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡？
- 2024-05-31全网首发第二弹！软考2024年5月《软件设计师》真题+解析+答案！（11-20题）
- 2024-05-31全网首发！软考2024年5月《软件设计师》真题+解析+答案！（21-30题）
