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

朱雀 2022-07-24 11:05 131阅读 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 条评论，131人围观）

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

相关阅读

相关算法题练习——JS Node+python题解判断一个链表是否为回文结构、单链表的排序

目录判断一个链表是否为回文结构单链表的排序 -------------------- 判断一个链表是否为回文结构描述 > 给定一个链表，请判断该链表是否为

﹏ヽ暗。殇╰゛Y/ 2024年04月05日 05:29/ 0 赞/ 28 阅读

相关判断是否是回文链表

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

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

相关判断回文链表

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

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

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

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

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

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

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

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

相关 C# 判断是否为回文

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

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

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

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

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

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

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

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

相关判断一个数是否为回文数C

判断一个数是否为回文数。设n是一任意自然数。若将n的各位数字反向排列所得自然数n1与n相等，则称n为一回文数。 \include<stdio.h> intmain()

小灰灰/ 2022年05月25日 12:29/ 0 赞/ 249 阅读

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

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

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