宁德营销型网站建设,网站关键字没有排名,搜索引擎优化是做什么的,苏州app软件开发公司目录
一.【Leetcode203】移除链表元素
1.链接
2.题目再现 A.双指针法
B.类尾删法
C.哨兵位
二.【Leetcode876】链表的中间节点
1.链接#xff1a;链表的中间节点
2.题目再现
3.解法#xff1a;快慢指针
三.链表中倒数第k个节点
1.链接#xff1a;链表中倒数第k个… 目录
一.【Leetcode203】移除链表元素
1.链接
2.题目再现 A.双指针法
B.类尾删法
C.哨兵位
二.【Leetcode876】链表的中间节点
1.链接链表的中间节点
2.题目再现
3.解法快慢指针
三.链表中倒数第k个节点
1.链接链表中倒数第k个节点
2.题目再现
3.解法 快慢指针 一.【Leetcode203】移除链表元素
1.链接
移除链表元素
2.题目再现 A.双指针法 1.创建一个指针 curhead 和一个指针 preNULL 2.用cur-val 与 val 比较,如果不相等则把 cur 赋给 pre 使cur 指向下一个节点即 curcur-next 3.如果相等则使 pre 的 next 指向 cur 的 next 即 pre-nextcur-next 然后再 free 掉 cur ,最后再使 cur 等于 pre 的 next注意在进行这些步骤之前要判断 pre 是否为空 若为空即为头删 演示
双指针代码
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode*preNULL;struct ListNode*curhead;while(cur){if(cur-val!val){precur;curcur-next;}else {if(preNULL){headcur-next;free(cur);curhead;}else {pre-nextcur-next;curpre-next;}}}return head;
}
B.类尾删法 1.创建一个新的指针newhead 同时为了省去找尾的麻烦我们可以定义一个尾指针 tail 来保存尾节点 2.再创建一个指针 cur head ,用来遍历链表 3.如果 cur-val ! val 则尾插 注意要判断 tail 是否为空 类似于单链表的尾插那部分如果不理解的话可查看文章 单链表的增删查改 4.如果 cur-val val则 curcur-next 5.最后要将尾节点置空。 演示
类尾插代码
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode *newheadNULL;struct ListNode*tailNULL;struct ListNode*curhead;while(cur){if(cur-val!val){if(tailNULL){newheadtailcur;}else {tail-nextcur;tailtail-next;}curcur-next;}else{curcur-next;}}if(tail){tail-nextNULL;}return newhead;
}
C.哨兵位 1.malloc 一个哨兵位节点 dummyhead使其 next 指向 head 2.再定义一个节点 tmp dummyhead 用这个遍历链表 3.注意因为 tmp -next 才是 head 所以 while 里要写 tmp-next !NULL 演示
移除链表元素 哨兵位法动态演示代码
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode*dummyhead(struct ListNode*)malloc(sizeof(struct ListNode));dummyhead-nexthead;struct ListNode*tmpdummyhead;while(tmp-next!NULL){if(tmp-next-valval){tmp-nexttmp-next-next;}else {tmptmp-next;}}return dummyhead-next;
} 二.【Leetcode876】链表的中间节点
1.链接链表的中间节点
2.题目再现 3.解法快慢指针 1.定义一个快指针 fast 和一个慢指针 slow 都初始化为 head; 2.遍历链表快指针一次走2步慢指针一次走1步 3.注意因为链表的长度可能是单数也可能是双数所以当我们已 fast 是否为NULL 作为循环控制条件的话要在 fast 走2步前判断 fast-next 是否为空 4.最后慢指针就是中间节点。 演示
链表中间节点 快慢指针动态演示代码
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode*slowhead;struct ListNode*fasthead;while(fast){if(fast-nextNULL) //注意判断{break;}else{fastfast-next-next; //fast 走2步}slowslow-next; //slow 走1步}return slow; //返回慢指针
} 三.链表中倒数第k个节点
1.链接链表中倒数第k个节点
2.题目再现 3.解法 快慢指针 1.定义一个快指针 fast 和一个慢指针 slow 都初始化为 head; 2.因为倒数第k个节点和尾节点的差为 k-1 所以我们先让快指针先走 k-1 步 或者因为尾节点所指向的NULL 和倒数第k个节点相差k也可以先让快指针走k步 这个时候慢指针不动 3.快指针走完后快指针和慢指针依次走每次只走1步 注意如果是k-1那么遍历结束的条件是fast-next 是否为空 如果是k那么遍历结束的条件是fast 是否为空 4.返回慢指针。 演示
链表倒数第K个节点 快慢指针动态演示代码
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{if(pListHeadNULL){return NULL;}struct ListNode*slowpListHead;struct ListNode*fastpListHead;while(k--) //这里以先走k步为例{if(fastNULL){return NULL;}fastfast-next;}while(fast){slowslow-next;fastfast-next;}return slow;
} 本篇文章到此就结束了若有错误或是建议欢迎小伙伴们指出 请多多支持博主哦~ 谢谢你的阅读~
