链表的回文结构

[编程题]链表的回文结构

热度指数：66389 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

1->2->2->1

返回：true

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

罅隙·

发表于 2022-03-19 22:13:14

一、解题思想我的解题思想很朴素：首先找到中间结点将中间结点后半部分倒置分别从头结点和尾结点向中间遍历，检测在达到中间时刻之间val的值是否都相等二、过程分解为什么说对一道会三道呢？因为找到中间结点是一道题目，倒置又是一道题目，做完整道题目又是一道题目，所以我们可以将这道题目利展开全文

北鼻子

发表于 2020-07-13 22:21:13

单链表判断是否回文题目描述思路三个指针，分别n1,n2,n3;三个指针不断往后移动。 1、总体思路找到中间节点，然后把后半个链表反转后与前半部分比较。（注意：奇数个链表的话是从中点的后一个节点逆置；偶数个链表的话从中间链表的节点逆置） 2、问题是如何找到中间节点使用快慢指展开全文

牛客65461158号

发表于 2022-06-08 21:17:47

思路： 1.万年不变判断链表是否为空（纯属个人习惯） 2.找中点：设置两个引用fast、slow从头开始走，fast每次走两个节点，slow每次走一个节点，当fast走到链表尾，slow正好走到链表中点。 3.翻转后段链表：设置一个cur引用，让他置于中点的下一个节点cur=slow.next，从c 展开全文

Black-K

发表于 2021-09-03 09:13:16

两种方法，第二种的话空间复杂度成O(N)了；； /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class Palindrome 展开全文

进击的猿员

发表于 2022-01-14 15:31:43

1,先找到中间节点, 2.从中间节点以后开始逆置 3.然后从中间节点向后迭代 4.如果是回文,返回true,否则返回false 5.欢迎大家访问我的博客,我也会分享我自己的学习之路 https://blog.csdn.net/m0_63111921/article/de 展开全文

万千少男的梦

发表于 2024-04-02 13:30:31

class PalindromeList { public: struct ListNode* prevnode(struct ListNode*head) { struct ListNode*n1,*n2,*n3; n1 = nullptr; 展开全文

秋天zzzzz

发表于 2024-10-05 16:57:13

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class PalindromeList { public: bool 展开全文

螺蛳粉只吃炸蛋的走风

发表于 2023-11-30 16:08:36

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class PalindromeList { public: boo 展开全文

牛客65461158号

发表于 2022-06-11 15:35:56

快慢指针做法： 1.设置快慢指针找到链表中点。 2.翻转链表后半段：在中点之后的一个节点开始逐个翻转。 3.从两头开始遍历，如果出现两个节点val值不同，则返回false,否则返回true. import java.util.*; /* public class ListNode { in 展开全文

牛客368378559号

发表于 2022-01-15 16:13:30

/* struct ListNode { int val; struct ListNode next; ListNode(int x) : val(x), next(NULL) {} };/ struct ListNode* middleNode(struct ListNode* head) { s 展开全文