当前位置:网站首页>LeetCode每日一练 —— OR36 链表的回文结构
LeetCode每日一练 —— OR36 链表的回文结构
2022-07-31 03:11:00 【飞向星的客机】
前言
Wassup guys!我是Edison
今天是 牛客 上的 nowcoder. OR36 链表的回文结构
Let’s get it!
1. 题目分析
对于一个链表,请设计一个时间复杂度为 O ( n ) O(n) O(n),额外空间复杂度为 O ( 1 ) O(1) O(1) 的算法,判断其是否为回文结构。
给定一个链表的头指针 A,请返回一个 bool 值,代表其是否为回文结构。
保证链表长度小于等于 900。
示例 1:
输入:[1,2,4,2,1]
返回:true
示例 2:
输入:[1,4,2,1]
返回:false
2. 思路分析
这道题很简单:
(1)找到链表的中间节点(奇数就是中间的那个,偶数就是中间的第二个);
(2)从中间节点开始逆置;
(3)让前半段和后半段进行比较;
假设我们的链表为:[1,2,4,2,1](如图所示)
第 1 步,定义 快慢指针,找到中间节点(动图演示)
注意:这里面找中间节点的方法,要分链表个数为 奇数 还是 偶数,具体可以参考 LeetCode每日一练 —— 876. 链表的中间结点
第 2 步,从 mid’ 开始,逆置后半段(动图演示)
注意:这里的逆置可以参考之前做过的一道题,LeetCode每日一练 —— 206. 反转链表
第 3 步,通过一个循环,让 head 节点和 mid 节点依次比较,相等就比较下一个,只要有一个节点为 空,那么就说明结束循环,返回 true(如图所示)。
相信到这里大家可能会有个疑惑,它们俩怎么会相等呢?head 走到 2 就结束了呀,而 mid 还要走到 4。
我们知道,链表的当前节点存储的是下一个节点的地址,也就是说从 head 开始,当 head 走到第 2 个节点时,里面存储的 数据 是 2,而存储的 指针 是指向下一个元素的地址,也就是指向 4 的地址;
为什么还能找到 4 的地址呢?
因为我们只对从 mid 开始的 后半段进行逆置 了,前半段又没有逆置,所以当 head 走到第 2 个节点时,里面存储的 数据 是 2,而存储的 指针 是指向下一个节点的地址,也就是数据为 4 的节点的地址(如图所示);
所以比较的过程动图演示
3. 代码实现
接口代码
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/
class PalindromeList {
public:
// 1、找到链表的中间节点
struct ListNode* middleNode(struct ListNode* head){
struct ListNode* slow, *fast;
slow = fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
// 2、从中间节点开始, 反转链表
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* cur = head;
struct ListNode* newHead = NULL;
while (cur) {
// 头插前保存cur的下一个节点
struct ListNode* curNext = cur->next;
// 头插
cur->next = newHead;
newHead = cur;
cur = curNext;
if (curNext) {
curNext = curNext->next;
}
}
return newHead;
}
// 让前半段和后半段进行比较
bool chkPalindrome(ListNode* A) {
struct ListNode* head = A;
struct ListNode* mid = middleNode(head); //找到中间节点
struct ListNode* newHead = reverseList(mid); //从中间节点开始逆置,并把逆置的结果给newhead
while (newHead) {
if (head->val != newHead->val) {
//如果原节点的val 不等于 新节点的val
return false; //返回
}
else {
head = head->next;
newHead = newHead->next;
}
}
return true;
}
};
提交结果
边栏推荐
猜你喜欢
TCP详解(二)
[C language] Preprocessing operation
Is interprofessional examination difficult?Low success rate of "going ashore"?Please accept this practical guide!
Multilingual settings of php website (IP address distinguishes domestic and foreign)
What skills do I need to learn to move from manual testing to automated testing?
【C语言】三子棋(经典解法+一览图)
Office automation case: how to automatically generate period data?
Detailed explanation of TCP (1)
5. SAP ABAP OData 服务如何支持 $filter (过滤)操作
学习DAVID数据库(1)
随机推荐
How to develop a high-quality test case?
els 方块向左移动条件判断
学习DAVID数据库(1)
观察者模式
解析小结—自用
5. SAP ABAP OData 服务如何支持 $filter (过滤)操作
C# remote debugging
Good place to download jar packages
VS QT——ui不显示新添加成员(控件)||代码无提示
【Cocos Creator 3.5】缓动系统停止所有动画
LeetCode简单题之找到和最大的长度为 K 的子序列
Uninstallation of mysql5.7.37 under CentOS7 [perfect solution]
测试中的误报和漏报同样的值得反复修正
LeetCode中等题之分数加减运算
The els block moves the boundary to the right, and accelerates downward.
原子操作 CAS
SQL injection Less54 (limited number of SQL injection + union injection)
2022牛客多校联赛第四场 题解
2022 Nioke Multi-School League Game 4 Solution
The distance value between two arrays of LeetCode simple questions