c语言中的小小白-CSDN博客c语言中的小小白关注算法,c++,c语言,贪心算法,链表,mysql,动态规划,后端,线性回归,数据结构,排序算法领域.
https://blog.csdn.net/bhbcdxb123?spm=1001.2014.3001.5343
给大家分享一句我很喜欢我话: 知不足而奋进,望远山而前行!!! 铁铁们,成功的路上必然是孤独且艰难的,但是我们不可以放弃,远山就在前方,但我们能力仍然不足,所有我们更要奋进前行!!! 今天我们更新了单链表相关题目内容, 🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝
先看一下这个题的题目描述,大概要求就是合并两个链表,然后输出这个新的链表,并且要按照递增的顺序进行,并且原链表中的顺序就是递增的,因此这个题就变得简单了许多。下面我们来说一下这个题的思路:
这个题的大致思路就是创建一个新的链表,然后遍历两个链表,最后得到这个新的链表,整体的思路是非常简单的,下面我们来实现一下这个代码。
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,这样上一个就踢出了。这样我们这个题的代码就实现了。