判断一个链表是否为回文结构

朱雀 2022-07-24 11:05 162阅读 0赞

## 判断一个链表是否为回文结构 – C++ ##

题目：  
给定一个链表头节点head，请判断是否为回文结构

例如：  
1->2->1 true  
1->2->2->1 true  
1->2->3->4->2->1 false

--------------------

## 解题思路及代码 ##

1、找到链表中间节点，然后将链表中间节点的右边所有节点放入一个栈中。  
2、然后从链表首节点和栈顶元素一一对比，不相等则return false。

--------------------

**算法C++代码：**

链表节点结构定义

typedef struct Node
    {
        int data;
        struct Node* next;
    }node, *pLinkedList;

--------------------

bool isHuiWen(pLinkedList head)
    {
        if (head == NULL || head->next == NULL)
            return true;
    
        pLinkedList right = head->next;//保存中间节点的下一个节点(若为偶数则为偏右的中间节点)
        pLinkedList cur = head;           //快指针
        while (cur->next != NULL && cur->next->next != NULL)
        {
            right = right->next;
            cur = cur->next->next;
        }
        //当链表总结点个数为奇数情况时：
        if (cur->next != NULL && cur->next->next == NULL)
            right = right->next;
    
        //将链表右边的节点放入一个栈中
        stack<pLinkedList>* s = new stack<pLinkedList>();
        while (right != NULL)
        {
            s->push(right);
            right = right->next;
        }
    
        //比较链表左右两边节点是否相等
        while (!s->empty())
        {
            if (head->next->data != s->top()->data)
                return false;
            s->pop();
            head = head->next;
        }
        return true;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，162人围观）

还没有评论，来说两句吧...

相关阅读

相关牛客在线编程101-13 判断一个链表是否为回文结构

题目给定一个链表，请判断该链表是否为回文结构。回文是指该字符串正序逆序完全一致。数据范围：链表节点数 0 \\le n \\le 10^50≤n≤10

心已赠人/ 2023年10月04日 19:39/ 0 赞/ 11 阅读

相关 Java——判断是否为回文

解题思路 1.构建一个单链表，定义两个引用 fast 和 slow ； ![在这里插入图片描述][20200329132507835.png] 2.找到链表的中间

Bertha 。/ 2023年07月18日 14:28/ 0 赞/ 1 阅读

相关判断是否是回文链表

回文链表：如1->2->3->2->1或1->2->2->1，注意1->2不是回文链表。给定一个链表，若是回文链表，返回true，若不是回文链表，返回false。思路分

怼烎@/ 2022年12月17日 10:52/ 0 赞/ 202 阅读

相关判断回文链表

/ 判断链表是不是回文链表比如链表是这样的1->2->3->3->2->1是回文链表使用二叉树的后序遍历思想，拷贝一个链表，后序遍历，然后和原来的链表进行比较

朴灿烈づ我的快乐病毒、/ 2022年10月29日 01:57/ 0 赞/ 234 阅读

相关 Leecode 请判断一个链表是否为回文链表。

文章目录题目代码改进题目 > 输入: 1->2->2->1 > 输出: true 代码 class Solution

梦里梦外;/ 2022年10月15日 12:53/ 0 赞/ 166 阅读

相关判断字符串是否为回文

描述 > 给定一个字符串，请编写一个函数判断该字符串是否回文。如果回文请返回true，否则返回false。解法一 > 这是一个偷懒的解法 function j

忘是亡心i/ 2022年09月09日 06:08/ 0 赞/ 314 阅读

相关 C# 判断是否为回文

using System; using System.Collections.Generic; using System.Linq; us

旧城等待，/ 2022年08月21日 02:26/ 0 赞/ 223 阅读

相关判断一个链表是否为回文结构

判断一个链表是否为回文结构 – C++ 题目：给定一个链表头节点head，请判断是否为回文结构例如： 1->2->1 true 1->2->2->1 t

朱雀/ 2022年07月24日 11:05/ 0 赞/ 163 阅读

相关链表问题——判断一个链表是否为回文结构

【题目】　　给定一个链表的头结点head，请判断该链表是否为回文结构　　例如：　　1->2->1 返回true 　　1->2->3 返回false 【代

╰+攻爆jí腚メ/ 2022年06月05日 07:55/ 0 赞/ 183 阅读

相关判断一个链表是否为回文结构（Java实现）

这个算法题意思很容易理解，就是一个链表的顺序和它反过来的顺序是一样的则是回文结构，否则不是。比如：1->2->3->2->1，链表结构反过来也是1->2->3->2->1，这就

川长思鸟来/ 2021年12月18日 08:23/ 0 赞/ 262 阅读