欢迎来到我的：世界
收录专栏：链表
希望作者的文章对你有所帮助，有不足的地方还请指正，大家一起学习交流 !
前言
- 在这里写的是有关链表的落坑题，详细写了我落坑的全过程，相信大家也都掉过坑，该专栏我会持续更新，感谢铁子们的支持。
-———————对过程全力以赴，对结果淡然处之
第一题：删除链表的倒数第n个节点
地址： oj题地址
解题思路：
- 1.暴力遍历：
我们先遍历一遍，找到该链表中有多少个节点(第一次遍历)，然后再第二次遍历找到倒数第n个节点，再进行删除，再返回原地址。这种方法可以说是这道题的比较简单的实现方法。再这里我想讲一下另一种方法：
2.三指针法：
先创造三个指针，tail指针，sur指针，dst指针，而sur，dst指针一开始指向是链表的起始地址，tail指针是指向sur指针前一个字节的地址，这就需要重新开辟一块空间其中的next 可以找到sur的地址；
起始时物理图：
注意：链表因为地址不是相连的，其地址可以看作是随机的，图中的地址都是我随便编的,只是为了方便更容易观察思路：先让dst指针向后走n个节点，这样的话，dst指针和sur指针就相距了n个节点，然后让这三个指针一起向后一次移动一个节点，直到dst指针指向空指针，这样的话，sur所指的就是倒数第n个节点(这一步观念很重要，一定要想清楚),这个时候有要删除的那个节点地址，也有该节点上一个节点的地址tail指针所指，那就可以很好的完成删除。
以上的是思路，下面来进行实现；结束时的物理图：
struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) {
// write code here
//sur指针是指向要删除的那个节点，dst是与sur保持间距n的，tail是sur前一个节点
struct ListNode* sur = head, *dst = head;
struct ListNode*tail =(struct ListNode*)malloc(sizeof(struct ListNode));
tail->next=sur;
//先让dst指针走n个节点
while (n--) {
dst = dst->next;
}
while (dst) {
//三个指针一起出发，tail指针始终指向sur指针前前一个节点
dst = dst->next;
sur = sur->next;
tail = tail->next;
}
//删除
if (head == sur) {
//如果sur没动说明要删的就在第一个
head = head->next;
sur = head->next;
} else {
//要删的只要找到sur指针的前一个节点，就可以让sur后一个节点与之相连
tail->next = sur->next;
}
return head;
}
第二题：链表的中间结点
地址：oj地址
解题思路：
- 1.暴力遍历法：
根据这道题的正常思路，肯定是先遍历一遍该链表的所有结点的个数，就可以得出中间点了，最后返回指向该点的地址；这种方法很寻常，在这里我就不具体讲了，我想具体讲下一种方法：- 2.快慢指针法：
该方法思路是：先设置两个指针：slow，fast，分别是快慢指针，首先两个指针都是指向链表的起始位置，slow向下一个结点移动，而fast向下两个结点移动，直到fast指针停下，那fast指针什么时候停呢，肯定有不同情况，如果链表的结点时偶数时，这时fast 走到空为止，而如果链表总结点时奇数时,这时fast走到尾结点停下。
----如为奇数时：逻辑图：
第一步：
第二步：
第三步
若为偶数时：
逻辑图:
第一步：
第二步：
第三步：
第四步：
代码：
struct ListNode* middleNode(struct ListNode* head ) {
// write code here
//设置快慢指针
struct ListNode*sur=head,*dst=head;
//当dst指针为空或dst指向的next为空就停下
while(dst && dst->next)
{
sur=sur->next;
dst=dst->next->next;
}
return sur;
}
第三题：合并两个排序的链表
地址：oj地址
解题思路：
首先链表和顺序表不同，有些思路是行不通的；但也有其优点，链表是由一个一个结点连起来的，可以随时拆下来的；
用归并的方法，我们可以先创造两个指针，让需要归并的两组链表由起始位置进行比较，较小值尾插入一个指针，另一个指针是找到需要插入的前一个结点，好方便尾插；
比较1<2，尾插入 1 ，如果是第一次插入，应该先让head指针和tail指针同时指向 1 的地址；如果不是第一次插入，那就是应该pHead1的地址给tail->next，然后让tail指针指向tail->next，最后让pHead1指向下一个结点；
- 然后是 2<3 ，尾插入2的地址；跟上面的步骤一样；
注意：这里之后就不是第一次插入，记得让tail指针指向tail的下一个结点；
后面的步骤几乎是一样的；
直到有一个链表没有了，在将剩下链表直接进行尾插入，就可以了；
最后返回head指针；
但是这就对了么？
不是的，还有一步我们忘记了，如果两个链表其中一个是空，那这个程序的结果肯定报错，所以我们还要在最开始进行判断，如果有其中一个为空，则直接返回另一个链表；
代码：
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
// write code here
//如果其中一个链表为空，则直接返回另一个链表
if(pHead1==NULL)
return pHead2;
if(pHead2==NULL)
return pHead1;
struct ListNode* head = NULL, *tail = NULL;
//判断哪个链表先为空，就跳出去
while (pHead1 && pHead2) {
if (pHead1->val < pHead2->val) {
if (tail == NULL) {
//第一次尾插
head = tail = pHead1;
} else {
//不是第一次尾插
tail->next = pHead1;
tail=tail->next;
}
//让篇pHead1指针找到下一个结点
pHead1 = pHead1->next;
} else {
if (tail == NULL) {
//第一次尾插
head = tail = pHead2;
} else {
//不是第一次尾插
tail->next = pHead2;
tail=tail->next;
}
//让篇pHead2指针找到下一个结点
pHead2 = pHead2->next;
}
}
//判断哪个链表先为空，然后让另一个链表直接尾插入；
if(pHead1)
tail->next=pHead1;
if(pHead2)
tail->next=pHead2;
return head;
}
总结
在这里感谢老铁们的观看，在这里小孩谢谢大家的支持，以上的题目都是基于小孩现在的能力来说，如果还有更好的方法的老铁，可以在评论区里面一起进行讨论哦，在后面随着小孩的知识储备越多，小孩肯定还会加以优化优化！！文章来源：https://www.toymoban.com/news/detail-661874.html
到了最后：
我还想告诉你：
------------对过程全力以赴，对结果淡然处之
也是对我自己讲的文章来源地址https://www.toymoban.com/news/detail-661874.html
到了这里，关于链表之第一回的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[数据结构]链表之单链表（详解）](https://imgs.yssmx.com/Uploads/2024/01/400368-1.png)
