【数据结构】----单链表相关题目【小白必看！！！】
c语言中的小小白-CSDN博客c语言中的小小白关注算法,c++,c语言,贪心算法,链表,mysql,动态规划,后端,线性回归,数据结构,排序算法领域.
https://blog.csdn.net/bhbcdxb123?spm=1001.2014.3001.5343
给大家分享一句我很喜欢我话： 知不足而奋进，望远山而前行！！！ 铁铁们，成功的路上必然是孤独且艰难的，但是我们不可以放弃，远山就在前方，但我们能力仍然不足，所有我们更要奋进前行！！！ 今天我们更新了单链表相关题目内容， 🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝
例题一：
合并两个有序链表（点击可直接跳转这个题哦^o^）
先看一下这个题的题目描述，大概要求就是合并两个链表，然后输出这个新的链表，并且要按照递增的顺序进行，并且原链表中的顺序就是递增的，因此这个题就变得简单了许多。下面我们来说一下这个题的思路：
这个题的大致思路就是创建一个新的链表，然后遍历两个链表，最后得到这个新的链表，整体的思路是非常简单的，下面我们来实现一下这个代码。
代码实现：
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
if(list1==NULL)
{
return list2;
}
if(list2==NULL)
{
return list1;
}
ListNode*newhead;
ListNode*newTail;
newhead=newTail=(ListNode*)malloc(sizeof(ListNode));
while(list1&&list2)
{
if(list1->val>list2->val)
{
newTail->next=list2;
newTail=newTail->next;
list2=list2->next;
}
else
{
newTail->next=list1;
newTail=newTail->next;
list1=list1->next;
}
}
if(list1)
{
newTail->next=list1;
}
if(list2)
{
newTail->next=list2;
}
ListNode*ret=newhead->next;
free(newhead);newhead=NULL;
return ret;
}这就是这个题的一个代码，思路就是首先我们要判断一下这两个链表是不是空链表，如果是空链表的话那么我们就直接返回另外一个链表就可以了，然后我们继续往下看，创建两个新的节点，newhead和newTail，记住这里我们还要对这两个进行动态内存分配，保证他们不会是空节点，然后这两个一个是用来返回的，另一个是用来往后进行的，我们就用newTail用来往下进行，下面用while循环遍历，然后遍历结束之后，我们还要检查一下此时的list1和list2是否是为空，不是空就要将他们剩余的节点加在我们的链表之后。最后用ret代替newhead，然后对newhead进行内存释放，防止内存泄露。
例题二：
链表的中间结点
这个题的要求就是让你找到链表的中间节点，然后返回中间节点及其后面的节点，要求也是非常明确，我们也能很容易的看出这个题要求我们使用快慢指针进行，什么是快慢指针。
快慢指针是一种常用于解决链表相关问题的算法技巧。它通常用于检测链表中是否存在环，或者找到链表中的中间节点等。 快慢指针的原理很简单：定义两个指针，一个快指针和一个慢指针，它们起始都指向链表的头节点。然后，快指针每次移动两步，慢指针每次移动一步。通过这种方式，快指针会比慢指针移动得更快。如果链表中存在环，快指针最终会追上慢指针；如果没有环，快指针会先到达链表的尾部。 这个算法的一个常见应用是判断链表是否有环。如果快指针和慢指针最终相遇，那么链表中就存在环；如果快指针到达了链表的尾部，那么链表中就不存在环。 另外，快慢指针也可以用来找到链表的中间节点。当快指针到达链表尾部时，慢指针正好指向链表的中间节点。 这种算法的时间复杂度通常是 O(n)，其中 n 是链表的长度。
代码实现：
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
ListNode*low=head,*fast=head;
while(fast&&fast->next)
{
low=low->next;
fast=fast->next->next;
}
return low;
} typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
ListNode*low=head,*fast=head;
while(fast&&fast->next)
{
low=low->next;
fast=fast->next->next;
}
return low;
}这道题的代码实现就非常简单了，就是定义一个快指针一个慢指针，然后对这个链表进行遍历，因为快指针每次要往后移动两个节点，因此while循环的条件应该是fast和fast->都不为NULL
例题三：
移除链表元素
这个题的题意也是非常的简单易懂，就是给你一个链表，然后给你一个val，将这个链表的等于这个val的节点全部移除，输出剩下的节点，这个题我们的思路也是创建一个新的链表，然后我们去遍历原链表，等于这个值就跳过，否则添加到新链表当中。
代码实现：
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
ListNode*pcur=head;
ListNode*newhead,*newTail;
newhead=newTail=NULL;
while(pcur)
{
if(pcur->val!=val)
{
if(newhead==NULL)
{
newhead=newTail=pcur;
}
else
{
newTail->next=pcur;
newTail=newTail->next;
}
}
pcur=pcur->next;
}
if(newTail!=NULL)
{
newTail->next=NULL;
}
return newhead;
}这个代码就可以实现题目中的要求了，但是要注意一点，就是比如遇到这种情况：head = [1,2,6,3,4,5,6], val = 6，那么while循环之后最后一位是不是很就是6了，而不是空指针，因为最后一个节点是val，所以while循环时不会进入if语句，所以此时newTail指向的就是6，所以输出就会出错，因此循环结束之后我们要判断最后一个是否是NULL，不是的话就要把它置为NULL。
这样就可以通过了。
例题四：
移除元素
这个题的题意也很简单，就是删除val
代码实现：
int removeElement(int* nums, int numsSize, int val) {
int left=0;
for(int right=0;right<numsSize;right++){
if(nums[right] != val){
nums[left] = nums[right];
left++;
}
}
return left;
}这个代码的实现也是非常的简单，就是一个双指针，right一直往后进行，然后left实在符合的时候对数组进行修改然后再往后遍历
例题五：
环形链表的约瑟夫问题
这个题相对于上面的两道题来说，要稍微难一些，因为这个题是一个环形链表问题，规则就是从第一个节点开始报数，报道某个数就退出，然后我们看一下这个题怎样做才最好呢。
代码实现：
typedef struct ListNode ListNode;
//创建新节点
ListNode*buynode(int x)
{
ListNode*node=(ListNode*)malloc(sizeof(ListNode));
if(node==NULL)
{
exit(1);
}
node->val=x;
node->next=NULL;
return node;
}
//创建带环链表
ListNode*cycle(int n)
{
ListNode*phead=buynode(1);//这里传一个1即可，因为题目要求是得到结果的位置，所以传一个位置即可
ListNode*ptail=phead;
for(int i=2;i<=n;i++)//这里从2开始，也是因为是位置
{
ptail->next=buynode(i);
ptail=ptail->next;
}
ptail->next=phead;
return ptail;
}
int ysf(int n, int m) {
ListNode*prev=cycle(n);
ListNode*pcur=prev->next;
int count=1;
while(pcur->next!=pcur)
{
if(count==m)
{
prev->next=pcur->next;
free(pcur);
pcur=prev->next;
count=1;
}
else {
{
prev=pcur;
pcur=pcur->next;
count++;
}
}
}
int res=pcur->val;
free(pcur);
pcur=NULL;
return res;
}这就是这道题的代码了，思路确实要麻烦不少，我们来分析一下，我们首先要创建一个环形链表，然后为每一个节点赋值，因为这里要求我们求出最后一个点的位置，所以我们先为第一个点赋值为1，然后for循环从2开始。最后for循环结束之后，再令最后一个点指向第一个节点，这样就实现了一个环形链表，然后我们开始进行while循环，因为我们要求是求出最后一个节点，所以剩下最后一个节点时它会指向自己，所以我们while循环的条件就是pcur->next!=pcur。
while循环中我们还需要一个count来记录，如果count==m，那么就令count=1，重新开始记，并将这个人踢出，否则正常进行，count+1。
while语句中第一个if语句的逻辑我们要搞清楚，就是我们令prev->next=pcur->next,这里的prev为pcur的上一个节点，这样我们就可以踢出pcur，将pcur释放掉，然后再令pcur=prev->next,这样上一个就踢出了。这样我们这个题的代码就实现了。
腾讯云开发者
