画图分析：回文链表
画图分析：回文链表
Happy coding!
Enjoy Algorithms
第16天，lc234题
一、题目
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；
否则，返回 false 。
- 模型：数组+双指针
二、 举一反三
2.1 双指针：5. 最长回文子串
- dp[start][end]=dp[start+1][end-1]; end-1 >=start+1
2.2 92. 反转链表 II
- 反转链I 是一个链表 移动到另外一个链表，完全翻转。
- 反转链表 II ，原地翻转 必须借助三指针中 ppre ，部分翻转。【0 n,m】 必须明确前面的空间位置。
2.3 25. K 个一组翻转链表
- 部分翻转 需要定义三指针，初始化：个完去不相同
- 在ptail追加
- 翻转一个情况
2.4 86. 分隔链表
- 部分翻转 需要定义三指针。初始化 2个相同
ptail =pcur;
ppre =pcur;
pcur =pcur->next;
- 在ptail追加
- 3 个情况 。比较大小
三、思路：算法描述
@笨猪爆破组
在哪里断点
- 问：什么情况下定义 ppre，还是pnext呢？ 答：单链全部翻转定义pnext，但是遇到部分翻转。例如 【n m】个 ，大于x不翻转 ，奇偶等。需要删除一个元素必须ppre
- 问：pcur 指向链表 第一个元素 和第二个元素有什么区别？
答：
- pcur指向第一个元素自然ppre == ptail 这样， 部分翻转通过ptail =ppre 必然出错。ptail移动 靠自己
- 当三个指针不相同时候，pcur 指向第二个元素。可以放下的 ptail =ppre
四、细节：最后大booss
func isPalindrome(head *ListNode) bool {
if head == nil || head.Next == nil {
return true
}
slow, fast := head, head
var prev *ListNode = nil
for fast != nil && fast.Next != nil {
prev = slow
slow = slow.Next
fast = fast.Next.Next
}
prev.Next = nil // 断开
// 翻转
var head2 *ListNode = nil
for slow != nil {
tmp := slow.Next
slow.Next = head2
head2 = slow
slow = tmp
}
// 比对
for head != nil && head2 != nil {
if head.Val != head2.Val {
return false
}
head = head.Next
head2 = head2.Next
}
return true
}
作者：xiao_ben_zhu
链接：https://leetcode-cn.com/problems/palindrome-linked-list/solution/shou-hua-tu-jie-hui-wen-lian-biao-kuai-man-zhi-zhe/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
/*
* @lc app=leetcode.cn id=234 lang=cpp
*
* [234] 回文链表
*/
// @lc code=start
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution
{
public:
bool isPalindrome(ListNode *head)
{
//01 check
if (nullptr == head || nullptr == head->next)
{
return head;
}
//02 define three node
ListNode *phead = head;
ListNode *pslow = head;
ListNode *pfast = head;
ListNode *ptemp = nullptr;
while (pfast && pfast->next)
{ //细节1 pfast->next 判断
ptemp = pslow;
pslow = pslow->next;
pfast = pfast->next->next;
}
ptemp->next = nullptr; //变成2个链表
//03 reverse of mid list
phead = nullptr;
pfast = pslow;
ptemp = nullptr;
while (pfast)
{
//phead->1(pfast)->2(ptemp)-3()
//细节：这里不需要固定头节点，但是依然需要头节点。
//phead 代替头节点phead =&dump。
//防止别人看懂懂系列 认为内存泄漏什么的
ptemp = pfast->next;
pfast->next = phead;
phead = pfast;
pfast = ptemp;
}
//02 compare
pslow = head;
pfast = phead;
while (pslow && pfast)
{
if (pslow->val != pfast->val)
{
return false;
}
pslow = pslow->next;
pfast = pfast->next;
}
//细节：相等的去判断
//虽然 pslow 和 pfast有可能不相等 【1 2】 【3 2 1 】【1 2 3】
return true;
}
};
// @lc code=end
bug1
- ListNode* pcur =pfast; 理解错误了，我翻转第二个链表。pslow ,你写成pfast 。检查不清楚呀！！！！
bug2:你感觉不需判断，结果感觉错误
- 只有一个节点 pfast->next 条件不满足，ptemp =null ，ptemp->next 直接core掉 。这么简单道理你，竟然检查不出来
这样写代码 跟初始化很大关系。
- 这样写代码很怪，必须严格要求 必须是三个 node，不然怎么写都不对
head(-1)->1--2
ListNode myhead;
myhead.next =head;
ListNode* phead =&myhead;
ListNode* ppre =head;
ListNode* pcur =head->next;
bu4:删除一个节点后 链表不是一个完整链表了
- 部分翻转 定义pnext是错误的。这个自己没有认真推理
- 【推理】在3节点后面 删除2 然后在1节点后面插入2。
- bug6:遍历一个链表 怎么还易漏元素呢。
分析：
定义时候 ppre == ptail，在移动时候 ptail =ptail 根本没有变化。
默认三路指针情况是：
教训：指向前面3个不同元素。这样才可以依次移动。才可以
ListNode* pcur =head;
ListNode* ppre =&myhead; //delete
ListNode* ptail =&myhead; //insert
- bug6:元素不没有翻转，并且还丢失了。
忘记ptail->next =pcur
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-09-03，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
