如何利用建站平台服务客户,青岛栈桥景点介绍,有哪些网站可以免费,网站推广有哪些方式#x1f525;个人主页#xff1a;Quitecoder
#x1f525;专栏#xff1a;Leetcode刷题 本节内容我们来讲解常见的几道单链表的题型#xff0c;文末会赋上单链表增删查#xff0c;初始化等代码 目录 1.移除链表元素2.链表的中间节点3.返回倒数第K个节点#xff1a;4.环…
个人主页Quitecoder
专栏Leetcode刷题 本节内容我们来讲解常见的几道单链表的题型文末会赋上单链表增删查初始化等代码 目录 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是出于以下几个原因 表示头节点之前链表的头节点之前没有节点所以在遍历开始之前prev指向“虚拟的”头节点之前的位置这在逻辑上用NULL表示 处理头节点可能被删除的情况如果链表的头节点第一个节点就是需要删除的节点那么在删除头节点后新的头节点将是原头节点的下一个节点。因为头节点没有前一个节点所以使用NULL作为prev的初始值可以帮助我们处理这种情况。在代码中如果发现头节点需要被删除cur-val val且prev NULL就将头节点更新为下一个节点 简化边界条件的处理通过将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*p1head;struct ListNode*p2head;while(k--){p1p1-next;}while(p1!NULL){p1p1-next;p2p2-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 题目描述 环形链表中寻找环的起始节点的算法是基于“快慢指针”策略。这个算法分为两个主要阶段 确定链表中是否存在环 使用两个指针slow和fast它们初始时都指向链表的头节点head。然后slow每次向前移动一个节点而fast每次向前移动两个节点。如果链表中存在环那么fast指针最终会再次与slow指针相遇因为fast指针会从后面追上slow指针。如果在任何时候fast指针遇到NULL表示链表尾部则链表中不存在环。 找到环的起始节点 当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.相交链表 题目描述 思路 相交链表指的是两个链表在某一点开始合并成一个链表。这意味着从相交点到链表的末尾这两个链表都具有相同的节点
解决相交链表问题的一个有效方法是使用两个指针遍历两个链表。以下是实现这一思路的步骤
创建两个指针
创建两个指针p1和p2分别指向两个链表的头节点
同步遍历链表
同时移动两个指针每步向前移动一次。如果一个指针到达链表末尾则将其移动到另一个链表的头节点继续遍历。这样两个指针会分别遍历两个链表的节点
相遇点或结束 如果两个链表相交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.随机链表的复制 题目描述 思路
遍历原链表为每个原节点创建一个新节点这个新节点有相同的值并将其插入到原节点和下一个原节点之间。
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-randomNULL;curr-next newNode;curr newNode-next;}更新新节点的random指针由于每个新节点都紧跟在其对应的原节点后面可以通过原节点的random指针找到新节点的random指针应该指向的节点 curr head;while (curr) {if (curr-random) {curr-next-random curr-random-next;}curr curr-next-next;}将混合链表拆分为原链表和复制链表恢复原链表并提取出复制链表
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.反转链表 题目描述 方法一迭代法
迭代法通过遍历链表逐个改变节点的指向来实现链表的反转。其基本思路如下 初始化三个指针prev指向当前节点的前一个节点初始为NULLcurr指向当前节点初始为链表的头节点headnext临时保存curr的下一个节点 遍历链表在遍历过程中逐个节点地改变指向直到curr为NULL 更新指针在每次迭代中首先保存curr的下一个节点next curr-next然后改变curr的指向curr-next prev。之后移动prev和curr指针前进一步prev currcurr next 更新头节点当遍历完成curr为NULL时prev指向的是新的头节点
struct ListNode* reverseList(struct ListNode* head)
{if(headNULL)return NULL;struct ListNode*prev,*cur,*_next;prevNULL;curhead;_nexthead-next;while(cur){cur-nextprev;prevcur;cur_next;if(_next)_next_next-next;}return prev;
}方法二递归法
递归法利用递归回溯的过程实现链表的反转。其基本思路如下 递归基如果链表为空或只有一个节点直接返回当前节点作为新的头节点。 递归步骤对于链表head-...-n1-n2-...-null假设从n1开始的链表已经被成功反转即head-n1-n2-...-newHead。我们的目标是将head节点放到最后即n1-head-null并将n1的next设置为null。 执行反转递归调用自身传入head-next作为新的链表头直到链表末尾。然后设置head-next-next head这实现了反转再将head-next设置为null断开原来的连接 返回新的头节点递归的最深处将返回新的头节点每层递归都返回这个头节点最终实现整个链表的反转
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
本节内容到此结束感谢大家阅读
