网站建设员性质,给wordpress加相册,网站响应式和非响应式,网站建设 广告推广一、移除链表元素
leetcode链接
题目描述#xff1a;
给你一个链表的头节点 head 和一个整数 val #xff0c;请你删除链表中所有满足 Node.val val 的节点#xff0c;并返回 新的头节点 。 思路#xff1a;
正常遍历#xff0c;找到value的值与题目中相同的结点去fr…一、移除链表元素
leetcode链接
题目描述
给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。 思路
正常遍历找到value的值与题目中相同的结点去free掉分为两种情况
第一种就是头结点就是value值直接将头节点指向next
第二种情况就是第二个结点开始是value需要有一个前结点指向value结点的下一个。
源码
struct ListNode* removeElements(struct ListNode* head, int val)
{//链表本身为空if(headNULL)return NULL;struct ListNode* prev NULL;while(1)//头节点开始就是值{if(head-valval){prevhead;headhead-next;free(prev);if(headNULL){return NULL;}}else{break;}}struct ListNode* cur head;while(cur)//从第二个开始才是value可以使用prev因为第一个不是value可以存储{//这一部分卡了好久if(cur-valval){prev-nextcur-next; struct ListNode* delcur;free(del);curprev-next;}else{prevcur;curcur-next;}}return head;
} 二、链表的中间结点
leetcode链接
题目描述
给你单链表的头结点 head 请你找出并返回链表的中间结点。
如果有两个中间结点则返回第二个中间结点。 思路
用快慢指针法。
进行一个循环先让快指针走两步然后让慢指针走一步直到快指针指向空或者快指针的next指向空这时候的慢指针就指向了中间结点并且也满足第二个结点。
代码
struct ListNode* middleNode(struct ListNode* head)
{//快慢指针快指针走两步慢指针走一步struct ListNode* slow head;struct ListNode* fast head;while(fastfast-next){fastfast-next-next;slowslow-next;}return slow;
} 三、链表中倒数第k个结点
牛客网链接
题目描述
输入一个链表输出该链表中倒数第k个结点。 思路
也是快慢指针的思想。
先让快指针走k步然后再让快指针和慢指针一起走直到快指针为空。
这题有一些注意细节的点比如k大于链表结点的个数k0但这些都是小细节主要思想还是快慢指针~ 代码
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {// write code hereif(pListHeadNULL||k0)//k0和链表为空的情况{return NULL;}struct ListNode* fastpListHead;struct ListNode* slowpListHead;while(k--)//先让快指针走k步{fastfast-next;if(fastNULL){break;}}if(k0)//k大于链表结点的个数的情况{return NULL;}while(fast){fastfast-next;slowslow-next;}return slow;
}
四、反转链表
leetcode链接
题目描述
给你单链表的头节点 head 请你反转链表并返回反转后的链表。 思路
顺序遍历链表从第一个结点开始进行尾插注意这里的尾插不是手撕单链表里面的pushback函数而是应该将结点一个一个取下来。
相当于我们又学习了另外一种尾插的方式不是直接改变头节点的值而是将原有的头节点指向新的头节点。
代码
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* newheadNULL;struct ListNode* nextNULL;//头插while(head){nexthead-next;head-nextnewhead;newheadhead;headnext;}return newhead;
} 五、合并两个有序链表
leetcode链接
题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 思路
将两个链表的第一个结点顺序比较取小的尾插到一个新的头结点上若一个提前结束则将另一个直接尾插到新链表上
代码
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(list1NULL){return list2;}if(list2NULL){return list1;}//取小的尾插//为何这题可以直接定义一个尾结点struct ListNode* newheadNULL;struct ListNode* tailNULL;while(list1 list2){if(list1-val list2-val){if(newheadNULL){newheadtaillist1;//tailnewhead-next;}else{tail-nextlist1;//taillist1-next;tailtail-next;}list1list1-next;}else{if(newheadNULL){tailnewheadlist2;//tailnewhead-next;}else{tail-nextlist2;tailtail-next;}list2list2-next;}} if(list1)//剩余直接尾插{//taillist1;tail-nextlist1;} if(list2){//taillist2;tail-nextlist2;}return newhead;
}
小心得
在数据结构的新篇章里注意的小细节更多最好将能考虑的情况都要考虑到不然调试起来比较麻烦。一般只有将头结点为空的情况下直接赋值等于其余一般都需要进行next链接。
