【Leetcode】单链表常见题

Alt

🔥个人主页：Quitecoder

🔥专栏：Leetcode刷题

Alt

本节内容我们来讲解常见的几道单链表的题型，文末会赋上单链表增删查，初始化等代码

目录

  • 1.移除链表元素
  • 2.链表的中间节点
  • 3.返回倒数第K个节点：
  • 4.环形链表（判断）
  • 5.环形链表（判断加返回）
      • 5.1环的起始节点推导过程
  • 6.相交链表
  • 7.随机链表的复制
  • 8.反转链表
      • 方法一：迭代法
      • 方法二：递归法
  • 9.合并两个有序链表

1.移除链表元素

题目链接： 203.移除链表元素
题目描述：在这里插入图片描述

首先，这道题需要删除元素，我可以初始化一个结构体指针cur进行遍历链表，对于每个节点，检查它的值是否等于val，如果cur指向的节点值等于val，则需要删除这个节点，这里一个结构体指针是不够的，是因为单链表的单向性，我们则需要再定义另一个指针prev来实现

首先，定义并初始化两个结构体指针：

struct ListNode* cur = head;
struct ListNode* prev = NULL;

定义两个指针cur（当前节点指针）和prev（前一个节点指针）。cur初始化为指向头节点head，而prev初始化为NULL

在这个删除链表中指定值节点的函数中，prev指针被初始化为NULL是出于以下几个原因：

  1. 表示头节点之前：链表的头节点之前没有节点，所以在遍历开始之前，prev指向“虚拟的”头节点之前的位置，这在逻辑上用NULL表示

  2. 处理头节点可能被删除的情况：如果链表的头节点（第一个节点）就是需要删除的节点，那么在删除头节点后，新的头节点将是原头节点的下一个节点。因为头节点没有前一个节点，所以使用NULL作为prev的初始值可以帮助我们处理这种情况。在代码中，如果发现头节点需要被删除（cur->val == val且prev == NULL），就将头节点更新为下一个节点

  3. 简化边界条件的处理：通过将prev初始化为NULL，我们可以用统一的方式处理需要删除的节点是头节点的情况和位于链表中间或尾部的情况。这样，当prev不是NULL时，就意味着我们不在头节点，可以安全地修改prev->next来跳过需要删除的cur节点

紧接着进行遍历过程：


while (cur != NULL) {if (cur->val == val) {struct ListNode* next = cur->next;free(cur);if (prev != NULL) {prev->next = next;}else{head = next;}cur = next;}else {prev = cur;cur = cur->next;}
}
  • 如果cur指向的节点值等于val，则需要删除这个节点。首先，保存cur的下一个节点到临时变量next中。如果prev不是NULL（即当前节点不是头节点），则将prev->next设置为next，跳过当前节点，从而将其从链表中删除。如果prev是NULL（即当前节点是头节点），则需要更新头节点head为next
  • 释放（删除）当前节点cur所占用的内存。
  • 将cur更新为next，继续遍历链表

节点值不等于val：如果当前节点值不等于val，则cur和prev都前进到下一个节点

2.链表的中间节点

题目链接： 876.链表的中间节点
题目描述：在这里插入图片描述

我们这道题用到了快慢指针的思路：
设置一个快指针，一次走两步，慢指针一次走一步，当节点个数为奇数时，意味着我的快指针指向尾节点，慢指针指向中间节点，此时的判断条件为快指针节点的next指针指向空
当节点个数为偶数时，意味着当我快指针刚好为空时，慢指针走到中间第二个节点，所以代码如下：

struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow = head;struct ListNode* fast = head;while (fast != NULL && fast->next != NULL) {fast = fast->next->next;slow = slow->next;}return slow;
}

注意

来看这个判断条件：

while (fast != NULL && fast->next != NULL)

这里能不能交换呢？：

while (fast->next != NULL && fast != NULL)

上面的代码片段错误之处在于 while 循环中条件判断的顺序。特别是在判断 fast 不为 NULL 以及 fast->next 不为 NULL 的时候

问题在于，当循环检查条件 fast->next != NULL && fast != NULL 时，它首先检查 fast->next 是否不为 NULL。如果 fast 本身是 NULL，那么尝试访问 fast->next 将会导致未定义行为（通常是一个访问违规错误，导致程序崩溃）。这是因为你试图访问一个 NULL 指针的成员，这在 C 和 C++ 中是不合法的。

正确的方式是首先检查 fast 是否为 NULL，然后再检查 fast->next 是否不为 NULL。这确保了代码不会试图在 NULL 指针上进行成员访问

3.返回倒数第K个节点：

题目链接： 面试题02.02.返回倒数第K个节点
题目描述：在这里插入图片描述

简单思路：

设置两个指针，一个先走k步，再两个指针同时前移直到前一个指向空

int kthToLast(struct ListNode* head, int k)
{struct ListNode*p1=head;struct ListNode*p2=head;while(k--){p1=p1->next;}while(p1!=NULL){p1=p1->next;p2=p2->next;}return p2->val;
}

4.环形链表（判断）

题目链接： 141.环形链表
题目描述：在这里插入图片描述

龟兔赛跑算法：
设置快指针一次前行两步，慢指针一次一步，若有环，则两个指针一定相遇：

bool hasCycle(struct ListNode *head) {struct ListNode* fast = head;struct ListNode* slow = head;while (fast != NULL && fast->next != NULL) {fast = fast->next->next; // 快指针每次前进两步slow = slow->next; // 慢指针每次前进一步if (fast == slow) { // 如果快慢指针相遇，表示链表有环return true;}}// 遍历完成没有找到环，返回 falsereturn false;
}

简单证明：当两个指针都入环时，快指针开始追赶慢指针，速度相差一，相对移动的距离为1，则一定能追上

5.环形链表（判断加返回）

题目链接： 142.环形链表II
题目描述：在这里插入图片描述

环形链表中寻找环的起始节点的算法是基于“快慢指针”策略。这个算法分为两个主要阶段：

  1. 确定链表中是否存在环：
    使用两个指针，slow和fast，它们初始时都指向链表的头节点head。然后，slow每次向前移动一个节点，而fast每次向前移动两个节点。如果链表中存在环，那么fast指针最终会再次与slow指针相遇（因为fast指针会从后面追上slow指针）。如果在任何时候fast指针遇到NULL（表示链表尾部），则链表中不存在环。

  2. 找到环的起始节点：
    当slow和fast指针相遇时，我们可以确定链表中存在环。但要找到环的起始节点，我们可以使用下面的方法：

    • 在slow和fast首次相遇后，将一个指针（比如slow2）放置在链表的起始处head，而将slow保留在相遇点。
    • 然后同时将slow2和slow每次向前移动一个节点，直到它们相遇。它们相遇的节点就是环的起始节点。

5.1环的起始节点推导过程

假设环外的长度（从头节点到环起始节点的长度）是L，从环起始节点到slow和fast首次相遇点的长度是S，环的剩余长度是R。因此，环的总长度C = S + R。
**在这里插入图片描述**

当slow和fast首次相遇时：

  • slow指针走过的长度是L + S。
  • fast指针走过的长度是L + S + nC，其中n是fast指针在环中绕行的次数。

因为fast指针走的距离是slow指针的两倍，所以我们有：

[2(L + S) = L + S + nC]

通过简化这个方程，我们得到：

[L + S = nC]

或者

[L = nC - S]

这个方程告诉我们从头节点到环的起始节点的距离L，等同于从首次相遇点继续前进直到再次回到环起始节点的距离（即n圈环长度减去首次相遇点到环起始节点的距离S）。这就是为什么当我们将一个指针放在链表头部，另一个保留在首次相遇点，它们以相同的速度移动时，它们相遇的点就是环的起始节点

struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *slow = head, *fast = head;while (fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;if (slow == fast) { struct ListNode *slow2 = head;while (slow2 != slow) {slow = slow->next;slow2 = slow2->next;}return slow; }}return NULL; 
}

6.相交链表

题目链接： 160.相交链表
题目描述：在这里插入图片描述

思路：
相交链表指的是两个链表在某一点开始合并成一个链表。这意味着从相交点到链表的末尾，这两个链表都具有相同的节点

解决相交链表问题的一个有效方法是使用两个指针遍历两个链表。以下是实现这一思路的步骤：

  1. 创建两个指针

创建两个指针，p1和p2，分别指向两个链表的头节点

  1. 同步遍历链表

同时移动两个指针，每步向前移动一次。如果一个指针到达链表末尾，则将其移动到另一个链表的头节点继续遍历。这样，两个指针会分别遍历两个链表的节点

  1. 相遇点或结束
    • 如果两个链表相交，p1和p2会在相交点相遇。这是因为p1和p2会遍历整个结构（两个链表的总长度），这样调整确保它们最终会有相同的遍历长度。当它们移动到相交点时，由于它们步调一致，因此会同时到达相交点。
    • 如果链表不相交，p1和p2最终都会到达各自链表的末尾并同时为NULL，这意味着它们没有相交点

假设链表A的非共享部分长度为a，链表B的非共享部分长度为b，两个链表的共享部分长度为c。当p1和p2遍历完各自的链表后，它们会分别遍历对方的链表，所以它们各自遍历的总长度是a + c + b。这意味着无论a和b的长度差异如何，它们最终会同时到达相交点或链表的末尾。这个方法的优点是，它不需要知道两个链表的长度，也不需要额外的存储空间，只需要两个指针即可解决问题

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{if (headA == NULL || headB == NULL) {return NULL;}struct ListNode *pA = headA, *pB = headB;while (pA != pB) {pA = pA == NULL ? headB : pA->next;pB = pB == NULL ? headA : pB->next;}return pA;
}

7.随机链表的复制

题目链接： 138.随机链表的复制
题目描述：在这里插入图片描述

思路：

  1. 遍历原链表，为每个原节点创建一个新节点：这个新节点有相同的值，并将其插入到原节点和下一个原节点之间。
if (!head) return NULL;  struct Node* curr = head;while (curr) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->val = curr->val;newNode->next = curr->next;newNode->random=NULL;curr->next = newNode;curr = newNode->next;}
  1. 更新新节点的random指针：由于每个新节点都紧跟在其对应的原节点后面，可以通过原节点的random指针找到新节点的random指针应该指向的节点
 curr = head;while (curr) {if (curr->random) {curr->next->random = curr->random->next;}curr = curr->next->next;}
  1. 将混合链表拆分为原链表和复制链表：恢复原链表，并提取出复制链表
struct Node* pseudoHead = (struct Node*)malloc(sizeof(struct Node));pseudoHead->next = head->next;struct Node* copyCurr = pseudoHead->next;curr = head;while (curr) {curr->next = curr->next->next;if (copyCurr->next) {copyCurr->next = copyCurr->next->next;}curr = curr->next;copyCurr = copyCurr->next;}struct Node* copiedHead = pseudoHead->next;free(pseudoHead); return copiedHead;

解释

  • 第一步：遍历原链表，对于每个节点创建一个新节点，将新节点插入原节点和原节点的下一个节点之间。

  • 第二步：再次遍历链表，这次是为了设置新节点的random指针。因为每个新节点都位于其对应的原节点之后，可以通过原节点的random指针直接找到对应新节点的random目标节点。

  • 第三步：将原链表和复制的链表分离。在这一步中，恢复原始链表的next指针，并将复制链表的next指针指向正确的节点

所以这道题只是逻辑复杂一点，并没有很难理解

8.反转链表

题目链接： 206.反转链表
题目描述：在这里插入图片描述

方法一：迭代法

迭代法通过遍历链表，逐个改变节点的指向来实现链表的反转。其基本思路如下：

  1. 初始化三个指针：prev（指向当前节点的前一个节点，初始为NULL），curr（指向当前节点，初始为链表的头节点head），next（临时保存curr的下一个节点）

  2. 遍历链表：在遍历过程中，逐个节点地改变指向，直到curr为NULL

  3. 更新指针：在每次迭代中，首先保存curr的下一个节点（next = curr->next），然后改变curr的指向（curr->next = prev）。之后，移动prev和curr指针前进一步（prev = curr，curr = next）

  4. 更新头节点：当遍历完成，curr为NULL时，prev指向的是新的头节点

struct ListNode* reverseList(struct ListNode* head) 
{if(head==NULL)return NULL;struct ListNode*prev,*cur,*_next;prev=NULL;cur=head;_next=head->next;while(cur){cur->next=prev;prev=cur;cur=_next;if(_next)_next=_next->next;}return prev;
}

方法二：递归法

递归法利用递归回溯的过程实现链表的反转。其基本思路如下：

  1. 递归基：如果链表为空或只有一个节点，直接返回当前节点作为新的头节点。

  2. 递归步骤：对于链表head->...->n1->n2->...->null，假设从n1开始的链表已经被成功反转，即head->n1<-n2<-...<-newHead。我们的目标是将head节点放到最后，即n1->head->null并将n1的next设置为null。

  3. 执行反转：递归调用自身，传入head->next作为新的链表头，直到链表末尾。然后设置head->next->next = head（这实现了反转），再将head->next设置为null（断开原来的连接）

  4. 返回新的头节点：递归的最深处将返回新的头节点，每层递归都返回这个头节点，最终实现整个链表的反转

struct ListNode* reverseListRecursive(struct ListNode* head) {// 递归基：如果链表为空或只有一个节点，没有反转的必要if (head == NULL || head->next == NULL) {return head;}// 递归步骤：假设head->next之后的链表已经被成功反转了struct ListNode* newHead = reverseListRecursive(head->next);// head->next此时指向反转后的链表的最后一个节点// 将其next指针指回head，完成对head节点的反转head->next->next = head;// 断开原来head指向head->next的指针，防止形成环head->next = NULL;// 每一层递归返回新的头节点return newHead;
}

9.合并两个有序链表

题目链接： 21.合并两个有序链表
题目描述：在这里插入图片描述

这里与我们归并排序的思路相似，设置两个指针分别遍历两个链表，取元素插入到新链表中，直到某个链表遍历完成

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode *new ;new->val = 0;new->next = NULL;struct ListNode *p3 = new;struct ListNode *p1 = list1, *p2 = list2;while (p1 && p2) {if (p1->val < p2->val) {p3->next = p1;p1 = p1->next;} else {p3->next = p2;p2 = p2->next;}p3 = p3->next;}p3->next = p1 ? p1 : p2;struct ListNode *result = new->next; // 保存合并后链表的头节点free(new); // 释放new节点占用的内存return result; // 返回合并后的链表头节点
}

p3->next = p1 ? p1 : p2;这一步也是后面的关键，我不知道哪个链表遍历完，剩余一个链表还剩元素，我就需要将剩下的元素整体接入新链表中，这里就用三目运算符，如果p1不为空，则指向p1剩余元素，如果p1为空，则指向p2

本节内容到此结束，感谢大家阅读！！！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/289670.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

It takes two (搜索)

It takes two (搜索)

本题链接&#xff1a;登录—专业IT笔试面试备考平台_牛客网 题目&#xff1a; 样例&#xff1a; 输入 3 4 AAAO AAAA AAAA 输出 NO 思路&#xff1a; 根据题目意思&#xff0c;如果存在的 A 联通不可以成为 矩形&#xff0c;输出 NO&#xff0c;否则输出 YES 这道题看数据范…
阅读更多...
windwos权限维持

windwos权限维持

1.php 不死马权限维持 <?php ignore_user_abort(); //关掉浏览器&#xff0c;PHP脚本也可以继续执行. set_time_limit(0);//通过set_time_limit(0)可以让程序无限制的执行下去 $interval 5; // 每隔*秒运行 do { $filename test.php; if(file_exists($filename)) { echo…
阅读更多...
你是工作了十年，还是工作一年，重复了十遍？

你是工作了十年，还是工作一年，重复了十遍？

你是工作了十年&#xff0c;还是工作一年&#xff0c;重复了十遍&#xff1f; 很多人刻舟求剑、画地为牢&#xff0c;就是缺少复盘意识。 没有复盘&#xff0c;没有进步。这是来自 B 站 Up 主檀东东Tango的复盘四步法&#xff1a; &#x1f449; https://www.bilibili.com/v…
阅读更多...
Leaflet 中创建一个二维地图

Leaflet 中创建一个二维地图

要在 Leaflet 中创建一个二维地图&#xff0c;需要以下步骤&#xff1a; 1. 引入 Leaflet 库 首先&#xff0c;你需要在 HTML 文件中引入 Leaflet 库的 CSS 和 JavaScript 文件。你可以从官方网站下载 Leaflet&#xff0c;或者通过 CDN 引入。 <!-- Leaflet CSS --> &…
阅读更多...
uni-app中web-view的使用

uni-app中web-view的使用

1. uni-app中web-view的使用 uni-app中的web-view是一个 web 浏览器组件&#xff0c;可以用来承载网页的容器&#xff0c;uni-app开发的app与web-view实现交互的方式相关简单&#xff0c;应用通过属性message绑定触发事件&#xff0c;然后在web-view的网页向应用 postMessage 触…
阅读更多...
高防服务器、高防IP、高防CDN的工作原理是什么

高防服务器、高防IP、高防CDN的工作原理是什么

高防IP高防CDN我们先科普一下是什么是高防。“高防”&#xff0c;顾名思义&#xff0c;就犹如网络上加了类似像盾牌一样很高的防御&#xff0c;主要是指IDC领域的IDC机房或者线路有防御DDOS能力。 高防服务器主要是比普通服务器多了防御服务&#xff0c;一般都是在机房出口架设…
阅读更多...
智能算法-遗传算法 学习笔记

智能算法-遗传算法 学习笔记

适应度的计算可类别为神经网络的目标函数&#xff0c;但此算法属于无监督学习&#xff0c;宏观来讲为搜寻最优解&#xff08;梯度&#xff09;的方式不同&#xff1f; 但神经网络中好像并不存在变异操作&#xff08;参数矩阵突变&#xff09;&#xff1f; 交叉的话残差网络ResN…
阅读更多...
文件夹无法压缩是怎么回事？很简单的一个小原因~

文件夹无法压缩是怎么回事？很简单的一个小原因~

电脑为什么显示没法压缩了&#xff0c;明明后台没有打开文件&#xff0c;却提示另一个程序正在使用文件&#xff0c;无法访问&#xff0c;压缩失败。 通常这种情况是因为后台有程序正在读取你准备压缩的文件&#xff0c;例如使用wps和office修改了word、excel、ppt等文件还未保…
阅读更多...
OpenHarmony实战开发-Web组件的使用

OpenHarmony实战开发-Web组件的使用

介绍 本篇Codelab使用ArkTS语言实现一个简单的免登录过程&#xff0c;向大家介绍基本的cookie管理操作。主要包含以下功能&#xff1a; 获取指定url对应的cookie的值。设置cookie。清除所有cookie。免登录访问账户中心。 原理说明 本应用旨在说明Web组件中cookie的管理操作。…
阅读更多...
第十四届蓝桥杯JavaA组省赛真题 - 互质数的个数

第十四届蓝桥杯JavaA组省赛真题 - 互质数的个数

解题思路&#xff1a; 快速幂 欧拉函数 快速幂比较常见于数据较大的取模场景&#xff0c;欧拉函数感觉还是有点抽象 注意&#xff1a; 取模的时候就不要简写了&#xff0c;例如&#xff1a;res res * a % mod;不要写成res * a % mod; import java.util.Scanner;public c…
阅读更多...
C++判断点是否在三角形内部

C++判断点是否在三角形内部

1.问题 判断点是否在三角形内部。 2.思路 计算向量AB和AP的叉积、向量BC和BP的叉积、向量CA和CP的叉积&#xff0c;如果所有的叉积符号相同&#xff0c;则点在三角形内部。 3.代码实现和注释 #include <iostream> #include <vector>// 计算两个二维向量的叉积 …
阅读更多...
蚂蚁庄园今日答案

蚂蚁庄园今日答案

蚂蚁庄园是一款爱心公益游戏&#xff0c;用户可以通过喂养小鸡&#xff0c;产生鸡蛋&#xff0c;并通过捐赠鸡蛋参与公益项目。用户每日完成答题就可以领取鸡饲料&#xff0c;使用鸡饲料喂鸡之后&#xff0c;会可以获得鸡蛋&#xff0c;可以通过鸡蛋来进行爱心捐赠。其中&#…
阅读更多...
基于JSP的辅导员工作管理系统

基于JSP的辅导员工作管理系统

基于JSP的辅导员工作管理系统的设计与实现 摘要 在这个大时代信息化的背景之下&#xff0c;涌现了许多的信息化的管理模式&#xff0c;形成了这个大时代背景下的独有的管理的形式和独具特色的管理的类型和模式。其中就包括信息化的员工工作的管理模式。现在越来越多的人们接受…
阅读更多...
电商打单ERP必备API列表-API调用指南

电商打单ERP必备API列表-API调用指南

1、打开淘宝开放平台API文档&#xff0c;查看API参数。 2、选择需要的API&#xff0c;进行测试对接。注册账号获取APIkey 3、进入API测试页&#xff0c;开始测试taobao.custom custom-自定义API操作 公共参数 名称类型必须描述keyString是调用key&#xff08;必须以GET方…
阅读更多...
Redis命令介绍

Redis命令介绍

一、redis启动&#xff1a; 本地启动&#xff1a;redis-cli 远程启动&#xff1a;redis-cli -h host -p port -a password Redis 连接命令 1 AUTH password 验证密码是否正确 2 ECHO message 打印字符串 3 PING 查看服务是否运行 4 QUIT 关闭当前连接 5 SELECT index 切换…
阅读更多...
如何用磁力仪探测管缆的位置和埋深？

如何用磁力仪探测管缆的位置和埋深？

不论是航空磁测&#xff0c;还是海洋磁测&#xff0c;都是直接测量磁场总强度T&#xff0c;而后以总磁异常ΔT成图。磁异常总强度Ta是磁场总强度T与正常场T0的矢量差&#xff0c;即&#xff1a; Ta&#xff1d; T&#xff0d; T0 根据参考文献1&#xff0c;2的推导&#xff0c…
阅读更多...
c++红黑树

c++红黑树

c红黑树 1. 红黑树的概念 红黑树&#xff0c;是一种二叉搜索树&#xff0c;但在每个结点上增加一个存储位表示结点的颜色&#xff0c;可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制&#xff0c;红黑树确保没有一条路径会比其他路径长出俩倍&…
阅读更多...
Qt消息机制和事件

Qt消息机制和事件

Qt消息机制和事件 Qt消息机制和事件--2 事件 事件&#xff08;event&#xff09;是由系统或者 Qt 本身在不同的时刻发出的。当用户按下鼠标、敲下键盘&#xff0c;或者是窗口需要重新绘制的时候&#xff0c;都会发出一个相应的事件。一些事件在对用户操作做出响应时发出&…
阅读更多...
基于JavaWEB SSM SpringBoot婚纱影楼摄影预约网站设计和实现

基于JavaWEB SSM SpringBoot婚纱影楼摄影预约网站设计和实现

基于JavaWEB SSM SpringBoot婚纱影楼摄影预约网站设计和实现 博主介绍&#xff1a;多年java开发经验&#xff0c;专注Java开发、定制、远程、文档编写指导等,csdn特邀作者、专注于Java技术领域 作者主页 央顺技术团队 Java毕设项目精品实战案例《1000套》 欢迎点赞 收藏 ⭐留言…
阅读更多...
【Java程序设计】【C00415】基于（JavaWeb）Springboot的家教管理系统（含论文）

【Java程序设计】【C00415】基于（JavaWeb）Springboot的家教管理系统（含论文）

基于&#xff08;JavaWeb&#xff09;Springboot的家教管理系统&#xff08;含论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 博主介绍&#xff1a;java高级开发&#xff0c;从事互联网行业六年&#xff0c;已经做了六年的毕业设计程序开发&#xff0c;开发过上千…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023