文档章节

回文链表

r
 ranjiewen
发布于 2016/11/03 23:52
字数 705
阅读 3
收藏 0

    回文链表其实也是链表反转的变形;也可以用栈实现。

//对于一个链表,请设计一个时间复杂度为O(n), 额外空间复杂度为O(1)的算法,判断其是否为回文结构。
//给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。
//测试样例:
//1->2->2->1
//返回:true

#include <stdio.h>
#include <iostream>
using namespace  std;

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};


//思路1:空间O(n) 整个链表遍历两边, 开一个栈,第一遍遍历把链表中每个元素push进栈中,这样堆中的元素的pop顺序就是链表的倒序输出;第二遍就开始pop栈中数据,每pop一个数据,就把这个数据跟链表中进行对比,如果相同继续往下走,如果不同返回false。
//
//思路2:空间O(1),使用快慢指针法,第一步设置一个块指针和一个慢指针,快指针一次走两步,慢指针一次走一步(慢),当快指针下一步为null的时候说明慢指针已经走了一半,这就可以找到中间节点。第二步反转中间链表后面的指针,第三部从头尾向中间扫描,对比每个元素是否相等,如果都相等,则是回文数,否则不是回文数。(下面网友易水给出了代码实现,这里不再叙述)

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
    
        ListNode* pSlow = A;
        ListNode* pQucik = A;
        //快慢指针找到中间节点
        while (pQucik!=nullptr&&pQucik->next!=nullptr)
        {
            pQucik = pQucik->next->next;
            pSlow = pSlow->next;
            
        }
        //将中点结点后的指针反转
        ListNode* pNode = nullptr;
        pNode = pSlow->next;
        ListNode* pHead = pSlow;  //反转链表的头
        while (pNode!=nullptr)   //测试未通过
        {
            ListNode* temp = pNode;
            pNode = pNode->next;
            temp->next = pHead;
            pHead = temp;
        }
        while (A!=pHead)
        {
            if (A->val!=pHead->val)
            {
                return false;
            }
            A = A->next;
            pHead = pHead->next;
        }
        return true;
    }
};

class PalindromeList1 {
public:
    bool chkPalindrome(ListNode* A) {  //A不带头节点
        // write code here
        if (A == nullptr || A->next == nullptr)
            return true;
        ListNode* head = nullptr;
        ListNode* node = A;

    /*    //将中间节点后的指针反转        
        ListNode* p = slow->next;
        ListNode* p1 = p->next;
        while (p != NULL){
            p->next = slow;
            slow = p;
            p = p1;
            p1 = p1->next;
        }*/

        while (node != nullptr){
            ListNode* temp = node;
            node = node->next;
            temp->next = head;
            head = temp;
        }
        while (A != nullptr&&head != nullptr){
            if (A->val != head->val){
                return false;
            }
            A = A->next;
            head = head->next;
        }
        return true;
    }
};

void print(ListNode* pHead)
{
    if (pHead==nullptr)
    {
        puts("链表为空!");
        return;
    }
    puts("链表为:");
    ListNode*pNode = pHead->next;
    while (pNode)
    {
        printf("%d ->", pNode->val);
        pNode = pNode->next;
    }
    cout << "NULL\n";
}

ListNode* create()
{
    ListNode* pHead, *pNode, *temp;
    int x;
    pHead = pNode = (ListNode*)malloc(sizeof(ListNode));  //带头节点的链表
    printf("请输入链表数据,以0为结束标志:\n");
    scanf("%d", &x);
    while (x)
    {
        temp = (ListNode*)malloc(sizeof(ListNode));
        temp->val = x;
        pNode->next = temp;
        pNode = temp;
        scanf("%d", &x);
    }
    pNode->next = nullptr;
    return pHead;
}


int main()
{
    ListNode *pHead = create();
    print(pHead);
    PalindromeList s;
    bool val=s.chkPalindrome(pHead);
    cout << val << endl;
    return 0;
}

 

本文转载自:http://www.cnblogs.com/ranjiewen/p/5629328.html

r
粉丝 1
博文 203
码字总数 28
作品 0
武汉
程序员
私信 提问
前端也来点算法(TypeScript版) | 2 - 回文数和回文链表

算法采用 TS 进行编写。 回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。回文链表是链表节点的值和回文数有相同规律的链表。 回文数 这个数字可以看成是以中心对称分布的。...

云影sky
09/16
0
0
java简单算法总结

1、翻转字符串 function reverseString(str) { }reverseString("hello"); 2、阶乘算法 public static int factorialize(int num) { } else { } } public static void main(String[] args......

晚天吹凉风
2017/12/18
15
0
LeetCode:Valid Palindrome - 回文字符串

1、题目名称 Valid Palindrome(回文字符串) 2、题目地址 https://leetcode.com/problems/valid-palindrome/ 3、题目内容 英文:Given a string, determine if it is a palindrome, consid......

北风其凉
2015/08/05
173
0
LeetCode:Palindrome Linked List - 回文链表

1、题目名称 Palindrome Linked List(回文链表) 2、题目地址 https://leetcode.com/problems/palindrome-linked-list/ 3、题目内容 英文:Given a singly linked list, determine if it i......

北风其凉
2015/12/18
366
0
判断一个链表是否为回文结构。(时间复杂度要求O(n),空间复杂度要求O(1))

题目要求: 对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。 给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度...

shs0708
2016/05/03
278
0

没有更多内容

加载失败,请刷新页面

加载更多

规则引擎

解决问题 版本迭代速度更不上业务变化,但是若多个业务同时变化,除了为每个业务设计专属配置项也不利于操作。就想服务接口单纯化,将复杂多变的业务逻辑交给规则引擎,让用户在web端或cs端自...

无极之岚
24分钟前
4
0
OSChina 周三乱弹 —— 欢迎你来做产品经理

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @巴拉迪维 :10多次劲歌金曲获奖,更多叱咤歌坛排名,黎明才应该是四大天王之首,只可惜拍的电影太少。单曲循环一个多月的歌,力荐 《无名份的...

小小编辑
今天
215
9
500行代码,教你用python写个微信飞机大战

这几天在重温微信小游戏的飞机大战,玩着玩着就在思考人生了,这飞机大战怎么就可以做的那么好,操作简单,简单上手。 帮助蹲厕族、YP族、饭圈女孩在无聊之余可以有一样东西让他们振作起来!...

上海小胖
今天
10
0
关于AsyncTask的onPostExcute方法是否会在Activity重建过程中调用的问题

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://blog.csdn.net/XG1057415595/article/details/86774575 假设下面一种情况...

shzwork
今天
7
0
object 类中有哪些方法?

getClass(): 获取运行时类的对象 equals():判断其他对象是否与此对象相等 hashcode():返回该对象的哈希码值 toString():返回该对象的字符串表示 clone(): 创建并返此对象的一个副本 wait...

happywe
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部