当前位置:网站首页>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;
}
};
提交结果
边栏推荐
- The els block moves the boundary to the right, and accelerates downward.
- Map.Entry理解和应用
- 想从手工测试转岗自动化测试,需要学习哪些技能?
- 11. Redis implements follow, unfollow, and follow and follower lists
- Annotation usage meaning
- 大小端模式
- [Android] Room - Alternative to SQLite
- els block to the right
- The simulation application of common mode inductance is here, full of dry goods for everyone
- 【HCIP】ISIS
猜你喜欢
华为分布式存储FusionStorage知识点总结【面试篇】
STM32 problem collection
The simulation application of common mode inductance is here, full of dry goods for everyone
Recursive query single table - single table tree structure - (self-use)
JS function this context runtime syntax parentheses array IIFE timer delay self.backup context call apply
IIR滤波器和FIR滤波器
刚出道“一战成名”,安全、舒适一个不落
What is distributed and clustered?What is the difference?
【Exception】The field file exceeds its maximum permitted size of 1048576 bytes.
VS QT——ui不显示新添加成员(控件)||代码无提示
随机推荐
Installation of mysql5.7.37 under CentOS7 [perfect solution]
execsnoop tool
C# remote debugging
What skills do I need to learn to move from manual testing to automated testing?
SocialFi 何以成就 Web3 去中心化社交未来
6. Display comments and replies
Discussion on Service Commitment of Class Objects under Multithreading
LeetCode simple problem to find the subsequence of length K with the largest sum
Graphical lower_bound & upper_bound
TCP/IP four-layer model
【C语言】进制转换一般方法
SQL injection Less46 (injection after order by + rand() Boolean blind injection)
递归查询单表-单表树结构-(自用)
Recursive query single table - single table tree structure - (self-use)
web容器及IIS --- 中间件渗透方法1
TCP详解(一)
YOLOV5 study notes (2) - environment installation + operation + training
刚出道“一战成名”,安全、舒适一个不落
Good place to download jar packages
The els block moves the boundary to the right, and accelerates downward.