当前位置:网站首页>Daily practice of LeetCode - palindrome structure of OR36 linked list
Daily practice of LeetCode - palindrome structure of OR36 linked list
2022-07-31 03:20:00 【airliner flying to the stars】
前言
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)找到链表的中间节点(The odd number is the one in the middle,An even number is the second in the middle);
(2)Invert from the middle node;
(3)Let the first half and the second half compare;
假设我们的链表为:[1,2,4,2,1](如图所示)
第 1 步,定义 快慢指针,找到中间节点(动图演示)
注意:Here's how to find an intermediate node,The number of linked lists to be divided is 奇数 还是 偶数,具体可以参考 LeetCode每日一练 —— 876. 链表的中间结点
第 2 步,从 mid’ 开始,逆置后半段(动图演示)
注意:The inversion here can refer to a question that was done before,LeetCode每日一练 —— 206. 反转链表
第 3 步,通过一个循环,让 head 节点和 mid Nodes are compared in turn,相等就比较下一个,As long as there is a node for 空,Then the cycle ends,返回 true(如图所示).
I believe that everyone here may have doubts,How can they be equal?head 走到 2 It's over,而 mid still to go 4.
我们知道,The current node of the linked list stores the address of the next node,也就是说从 head 开始,当 head 走到第 2 个节点时,里面存储的 数据 是 2,而存储的 指针 是指向下一个元素的地址,也就是指向 4 的地址;
为什么还能找到 4 的地址呢?
Because we only follow mid 开始的 The second half is reversed 了,No reversal in the first half,所以当 head 走到第 2 个节点时,里面存储的 数据 是 2,而存储的 指针 is the address to point to the next node,That is, the data is 4 的节点的地址(如图所示);
So the comparison process animation shows
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;
}
// Let the first half and the second half compare
bool chkPalindrome(ListNode* A) {
struct ListNode* head = A;
struct ListNode* mid = middleNode(head); //找到中间节点
struct ListNode* newHead = reverseList(mid); //Invert from the middle node,And give the result of the inversionnewhead
while (newHead) {
if (head->val != newHead->val) {
//如果原节点的val 不等于 新节点的val
return false; //返回
}
else {
head = head->next;
newHead = newHead->next;
}
}
return true;
}
};
提交结果
边栏推荐
- 刚出道“一战成名”,安全、舒适一个不落
- Day32 LeetCode
- 安全20220722
- 3.5 】 【 Cocos Creator slow operating system to stop all animations
- With 7 years of experience, how can functional test engineers improve their abilities step by step?
- 遗留系统的自动化策略
- CloudCompare&PCL 计算两个点云之间的重叠度
- Golang中的addressable
- Thesis framework of the opening report
- The distance value between two arrays of LeetCode simple questions
猜你喜欢
MultipartFile文件上传
什么是系统?
【编译原理】词法分析程序设计原理与实现
Mysql 45讲学习笔记(二十四)MYSQL主从一致
A brief introduction to the showDatePicker method of the basic components of Flutter
STM32 problem collection
刚出道“一战成名”,安全、舒适一个不落
postgresql 15源码浅析(5)—— pg_control
A brief introduction to the CheckBox component of the basic components of Flutter
Key Technologies of Interface Testing
随机推荐
some of my own thoughts
分布式系统架构需要解决的问题
[C language] Three-pointed chess (classic solution + list diagram)
Several common errors when using MP
Compile Hudi
Annotation usage meaning
SQL injection Less46 (injection after order by + rand() Boolean blind injection)
原子操作 CAS
【动态规划】连续子数组的最大和
[Dynamic programming] Maximum sum of consecutive subarrays
Detailed explanation of TCP (2)
安全20220715
Day32 LeetCode
LeetCode简单题之找到和最大的长度为 K 的子序列
Redis 统计用户新增和留存
【C语言】预处理操作
STM32问题合集
点云DBSCAN聚类(MATLAB,非内置函数)
Mysql 45 study notes (twenty-five) MYSQL guarantees high availability
MP使用时的几个常见报错