江门网站优化经验,类qq留言网站建设,房源网,网站开发自定义模块#x1f440;樊梓慕#xff1a;个人主页 #x1f3a5;个人专栏#xff1a;《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》
#x1f31d;每一个不曾起舞的日子#xff0c;都是对生命的辜负。 目录
前言#xff1a;
【LeetCode】203.移除链表元素
【LeetCo… 樊梓慕个人主页 个人专栏《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》
每一个不曾起舞的日子都是对生命的辜负。 目录
前言
【LeetCode】203.移除链表元素
【LeetCode】206.反转链表 思路一
思路二
【LeetCode】876.链表的中间结点
快慢指针法
【LeetCode】剑指Offer 22.链表中倒数第k个结点
快慢指针法
【LeetCode】21.合并两个有序链表
【LeetCode】剑指Offer Ⅱ 27.回文链表 前言
本系列博文博主会讲解链表的经典OJ题目。
欢迎大家收藏以便未来做题时可以快速找到思路巧妙的方法可以事半功倍。 GITEE相关代码fanfei_c的仓库 【LeetCode】203.移除链表元素
原题链接移除链表元素 题目给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。 要想删除当前元素需要知道当前元素的位置及前一个元素的位置并且保存下一个元素的位置。
所以我们需要三个指针
一个指针命名为cur作用是遍历一个指针命名为prev指向位置为cur的前一个位置作用是删除prev-nextcur-next一个next指针用来保存cur的后一个位置确保free掉cur后仍然可以找到下一元素。
代码实现 /*
解题思路从头节点开始进行元素删除每删除一个元素需要重新链接节点
*/
struct ListNode* removeElements(struct ListNode* head, int val) {if(head NULL)return NULL;struct ListNode* cur head;struct ListNode* prev NULL;while(cur){//如果当前节点是需要删除的节点if(cur-val val){//首先保存下一个节点struct ListNode* next cur-next;//如果删除的为头节点更新头节点//否则让当前节点的前趋节点链接next节点if(prev NULL){head cur-next;}else{prev-next cur-next; }//释放当前节点让cur指向nextfree(cur);cur next;}else{//如果cur不是需要删除的节点则更新prev,curprev cur;cur cur-next;}}return head;
} 注意考虑极端情况如首个位置就是val的情况作单独处理。 【LeetCode】206.反转链表
原题链接反转链表 题目给你单链表的头节点 head 请你反转链表并返回反转后的链表。 思路一
同样的我们需要三个指针来完成这一操作
一个指针命名为cur作用是遍历一个指针命名为prev作用是拿到cur的前一个地址而后改变cur-next指向prev一个指针命名为next作用是保存cur的后一个位置防止修改cur-next后找不到cur的后一个位置。 代码实现 struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* prev NULL;struct ListNode* cur head, * next head;if (cur)// 检查cur是否为空{next cur-next;}while (cur){// 往后走prev cur;cur next;if(next)// 检查next是否为空next next-next;}return prev;
} 思路二
取结点头插完成逆置。
大家只要掌握了头插就很简单了。
代码实现 // 取节点头插的思想完成逆置
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* newhead NULL;struct ListNode* cur head;while(cur){struct ListNode* next cur-next;//头插新节点更新头cur-next newhead;newhead cur;cur next;}return newhead;
} 【LeetCode】876.链表的中间结点
原题链接链表的中间结点 题目给你单链表的头结点 head 请你找出并返回链表的中间结点。 如果有两个中间结点则返回第二个中间结点。 快慢指针法
若想找到中间结点我们可以定义两个指针
一个命名为slow令slow每次走一步一个命名为fast令fast每次走两步。
这样当fast为NULL或fast-next为NULL时slow恰好处于中间位置最后返回slow即可。
代码实现
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slowhead;struct ListNode* fasthead;while(fast fast-next)// 分别为奇数个与偶数个的判断条件{slowslow-next;fastfast-next-next;}return slow;
} 【LeetCode】剑指Offer 22.链表中倒数第k个结点
原题链接链表中倒数第k个结点 题目输入一个链表输出该链表中倒数第k个节点。 快慢指针法
同样需要快慢指针的方法。
令fast先走k步slow不动然后slow与fast同时向后走直到fast为NULL此时slow的位置就是倒数第k个位置。
代码实现
struct ListNode* getKthFromEnd(struct ListNode* head, int k)
{struct ListNode* slowhead,* fasthead;while(k--){if(fastNULL){return NULL;} fastfast-next;}while(fast){slowslow-next;fastfast-next;}return slow;
} 【LeetCode】21.合并两个有序链表
原题链接合并两个有序链表 题目将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 思路取小的尾插。 注意极端情况的判断如其中一个链表为空等等。
代码实现
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(list1NULL)// 判断其中一个链表为空的情况{return list2;}if(list2NULL)// 判断其中一个链表为空的情况{return list1;}struct ListNode* headNULL,*tailNULL;while(list1 list2){if(list1-vallist2-val){if(headNULL)// 头结点直接赋值{headtaillist1;}else// 尾插{tail-nextlist1;tailtail-next;}list1list1-next;}else{if(headNULL)// 头结点直接赋值{headtaillist2;}else// 尾插{tail-nextlist2;tailtail-next;}list2list2-next;}}if(list1)// list1有剩余{tail-nextlist1;}if(list2)// list2有剩余{tail-nextlist2;}return head;
} 【LeetCode】剑指Offer Ⅱ 27.回文链表
原题链接回文链表 题目给定一个链表的 头节点 head 请判断其是否为回文链表。 如果一个链表是回文那么链表节点序列从前往后看和从后往前看是相同的。 思路找到中间结点将后半部分逆置最后令前后两部分一一对比如果结点的值全部相同则为回文。 刚好我们可以利用上面实现过的函数链表的中间结点和反转链表。
代码实现
// 找到中间结点
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow head;struct ListNode* fast head;while (fast fast-next){slow slow-next;fast fast-next-next;}return slow;
}// 反转一个单链表
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* tail NULL;struct ListNode* cur head, * next head;while (next){next cur-next;cur-next tail;tail cur;cur next;}return tail;
}// 判断回文结构
bool isPalindrome(struct ListNode* head)
{struct ListNode* midmiddleNode(head);struct ListNode* newheadreverseList(mid);while(head newhead){if(head-val!newhead-val){return false;}else{headhead-next;newheadnewhead-next;}}return true;
} 如果你对该系列文章有兴趣的话欢迎持续关注博主动态博主会持续输出优质内容
博主很需要大家的支持你的支持是我创作的不竭动力
~ 点赞收藏关注 ~
