网站建设 分析,工程招标平台,电子网站建设心得,公司邮箱签名模板正如标题所说#xff0c;本文会图文详细解析三道单链表OJ题#xff0c;分别为#xff1a; 反转链表 #xff08;简单#xff09; 链表的中间节点 #xff08;简单#xff09; 链表的回文结构 #xff08;较难#xff09;
把他们放在一起讲的原因是#xff1a; 反转链…正如标题所说本文会图文详细解析三道单链表OJ题分别为 反转链表 简单 链表的中间节点 简单 链表的回文结构 较难
把他们放在一起讲的原因是 反转链表 和 链表的中间节点 是 链表的回文结构 的基础
为什么这样说请往下看 目录 1. 反转链表 做题思路 画图理解 代码实现 2. 链表的中间节点 做题思路 画图理解 代码实现 3. 链表的回文结构 做题思路 画图理解 代码实现 1. 反转链表 LeetCode链接206. 反转链表 - 力扣LeetCode 做题思路
遍历链表改变每个节点的链接方向使其链向前节点如果是第一个节点使其链向 NULL 这里需要3个指针 cur 指向当前需要修改的节点 prev 记录 cur 的前一个节点 cur 要链向此节点 next 记录 cur 的后一个节点避免 cur 改变链接方向后找不到下个节点
画图理解 ✍️代码实现
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* cur head;struct ListNode* prev NULL;while (cur ! NULL){struct ListNode* next cur-next;cur-next prev;prev cur;cur next;}return prev;
}
最后提交代码试试 完美通过本题并不难来搞下一题 2. 链表的中间节点 LeetCode链接876. 链表的中间结点 - 力扣LeetCode 做题思路
快慢指针搞两个指针一个叫 fast 一个叫 slow 快指针 fast 一次走两步慢指针 slow 一次走一步当 fast 走到 NULL 时 slow 恰好在中间此时 slow 指向的节点就是中间节点
画图理解 ✍️代码实现
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow head;struct ListNode* fast head;while (fast ! NULL fast-next ! NULL){slow slow-next;fast fast-next-next;}return slow;
}
提交代码 这道题也很简单主要就是快慢指针的思路第一次接触的话可能想不到这种方法
接下来就是本文重点了前面这些只是开胃小菜 3. 链表的回文结构 牛客链接链表的回文结构_牛客题霸_牛客网 (nowcoder.com) 做题思路
1. 找到中间节点
2. 反转中间节点及其之后的链表
3. 此时把链表分为两段
未反转的链表为一段用指针 list1 指向这段链表的头节点反转过的链表为另一段用指针 list2 指向这段链表的头节点
4. 比较 list1 和 list2 节点的值是否相等
如果相等 list1 和 list2 同时往后走去比较下一组数据如果不相等说明链表不是回文结构返回 false
5. 当 list2 走到 NULL 处时说明此链表是回文结构返回 true
画图理解 可以看到本题需要调用之前写过的代码
这就是为什么我说前两道题是本题的基础
✍️代码实现
//找链表的中间节点
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow head;struct ListNode* fast head;while (fast ! NULL fast-next ! NULL){slow slow-next;fast fast-next-next;}return slow;
}//反转链表
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* cur head;struct ListNode* prev NULL;while (cur ! NULL){struct ListNode* next cur-next;cur-next prev;prev cur;cur next;}return prev;
}//牛客这道题不支持用C语言答题
//虽然我们还没有学C但是C是兼容C的
//直接用C的方式写代码即可
class PalindromeList
{
public:bool chkPalindrome(ListNode* head){struct ListNode* list1 head;struct ListNode* mid middleNode(head);struct ListNode* list2 reverseList(mid);while (list2 ! NULL){if (list1-val ! list2-val){return false;}list1 list1-next;list2 list2-next;}return true;}
};
提交代码 成功通过
怎么样大家看到这里把这三道题弄懂了吗如果有问题可以在评论区留言哦 :D 本文完
