C++数据结构与算法之判断一个链表是否为回文结构的方法
本文实例讲述了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; }
希望本文所述对大家C++程序设计有所帮助。
相关推荐
-
C++数据结构与算法之反转链表的方法详解
本文实例讲述了C++数据结构与算法之反转链表的方法.分享给大家供大家参考,具体如下: 算法概述:要求实现将一条单向链表反转并考虑时间复杂度. 算法分析: 数组法(略): 将列表元素逐个保存进数组,之后再逆向重建列表 点评:实现逻辑最简单,需要额外的内存开销. 移动指针: 通过三个指针逐个从链表头开始逐一反转链表元素的指针 点评:不需要额外的内存开销,会改变原始链表. 递归: 以递归的方式首先找到链表尾部,再逐一反转指针 点评:不需要额外的内存开销,不会改变原始链表. 算法实现: 构建链表结构 /
-
C++数据结构之链表的创建
C++数据结构之链表的创建 前言 1.链表在C/C++里使用非常频繁, 因为它非常使用, 可作为天然的可变数组. push到末尾时对前面的链表项不影响. 反观C数组和std::vector, 一个是静态大小, 一个是增加多了会对之前的元素进行复制改写(线程非常不安全). 2.通常创建链表都是有next这样的成员变量指向下一个项, 通过定义一个head,last来进行链表创建. 参考函数 TestLinkCreateStupid(). 说明 1.其实很早就知道另一种创建方式, 但是一直没总结. 没
-
C++ 数据结构链表的实现代码
C++ 链表 之前一直没怎么在意C++中的链表,但是突然一下子让自己写,就老是出错.没办法,决定好好恶补一下该方面的知识,也为今后的数据结构大下个良好的基础,于是我总结出以下几点,有些地方可能不正确,还望大家不吝赐教,旨在共同进步. 总结: 1.链表List的基本单元是节点Node,因此想要操作方便,就必须为每一步打好基础,Node的基本结构如下: class Node{ public: int data; Node *next; Node(int da=0,Node *p=NULL){ thi
-
C++数据结构与算法之判断一个链表是否为回文结构的方法
本文实例讲述了C++判断一个链表是否为回文结构的方法.分享给大家供大家参考,具体如下: 题目: 给定一个链表头节点head,请判断是否为回文结构 例如: 1->2->1 true 1->2->2->1 true 1->2->3->4->2->1 false 解题思路及代码 1.找到链表中间节点,然后将链表中间节点的右边所有节点放入一个栈中. 2.然后从链表首节点和栈顶元素一一对比,不相等则return false. 算法C++代码: 链表节点结构
-
Python数据结构与算法之列表(链表,linked list)简单实现
Python 中的 list 并不是我们传统(计算机科学)意义上的列表,这也是其 append 操作会比 insert 操作效率高的原因.传统列表--通常也叫作链表(linked list)--通常是由一系列节点(node)来实现的,其每一个节点(尾节点除外)都持有一个指向下一个节点的引用. 其简单实现: class Node: def __init__(value, next=None): self.value = value self.next = next 接下来,我们就可使用链表的结构来
-
Python编程判断一个正整数是否为素数的方法
本文实例讲述了Python编程判断一个正整数是否为素数的方法.分享给大家供大家参考,具体如下: import string import math #判断是否素数的函数 def isPrime(n): if(n<2): return False; elif(n==2): return True; elif(n>2): for d in range(2,int(math.ceil(math.sqrt(n))+1)): if(n%d==0): return False; return True;
-
Python实现判断一个字符串是否包含子串的方法总结
本文实例总结了Python实现判断一个字符串是否包含子串的方法.分享给大家供大家参考,具体如下: 1.使用成员操作符 in >>> s='nihao,shijie' >>> t='nihao' >>> result = t in s >>> print result True 2.使用string模块的find()/rfind()方法 >>> import string >>> s='nihao,s
-
Python cookbook(数据结构与算法)将序列分解为单独变量的方法
本文实例讲述了Python cookbook(数据结构与算法)将序列分解为单独变量的方法.分享给大家供大家参考,具体如下: 如果对象是可迭代的(任何序列),则可以进行分解操作,包括元组.列表.字符串.文件.迭代器以及生成器,可通过简单的一个赋值操作分解为单独的变量. 唯一要求:变量的总数和序列相吻合,否则将出错: Python 2.7.11 (v2.7.11:6d1b6a68f775, Dec 5 2015, 20:32:19) [MSC v.1500 32 bit (Intel)] on wi
-
Python cookbook(数据结构与算法)实现查找两个字典相同点的方法
本文实例讲述了Python实现查找两个字典相同点的方法.分享给大家供大家参考,具体如下: 问题:寻找两个字典中间相同的地方(相同的键.相同的值等) 解决方案:通过keys()或者items()方法来执行常见的集合操作(比如求并集.交集和差集) >>> a={'x':1,'y':2,'z':3} >>> b={'ww':10,'x':11,'y':2} >>> a.keys()& b.keys() #键的交集 {'y', 'x'} >>
-
Python cookbook(数据结构与算法)将名称映射到序列元素中的方法
本文实例讲述了Python将名称映射到序列元素中的方法.分享给大家供大家参考,具体如下: 问题:希望通过名称来访问元素,减少结构中对位置的依赖性 解决方案:使用命名元组collections.namedtuple().它是一个工厂方法,返回的是python中标准元组类型的子类,提供给它一个类型名称以及相应的字段名称,它就返回一个可实例化的类,为你以定义好的字段名称传入值等. 命名元组的主要作用在于将代码同它所控制的元素位置间进行解耦 >>> from collections import
-
php判断一个数组是否为有序的方法
本文实例讲述了php判断一个数组是否为有序的方法.分享给大家供大家参考.具体分析如下: 这段代码的时间复杂度为O(n) <?php function JudegSortArray($array) { if ($array [0] > $array [1]) { $flag = 1; } else { $flag = 0; } $temp = $flag; $len = count ( $array ); for($i = 1; $i < $len; $i ++) { if ($flag
-
java判断一个文件是否为二进制文件的方法
本文实例讲述了java判断一个文件是否为二进制文件的方法.分享给大家供大家参考.具体如下: public static boolean isBinary(File file) { boolean isBinary = false; try { FileInputStream fin = new FileInputStream(file); long len = file.length(); for (int j = 0; j < (int) len; j++) { int t = fin.rea
-
python判断一个变量是否已经设置的方法
python判断一个变量是否已经设置的方法:可以使用locals()函数来进行判断. locals()函数会以字典类型返回当前位置的全部局部变量,具体使用方法如:['testvar' in locals().keys()]. 方法如下: 第一种方法使用内置函数locals(): locals():获取已定义对象字典 'testvar' in locals().keys() 第二种方法使用内置函数dir(): dir():获取已定义对象列表 'testvar' in dir() 第
随机推荐
- oracle查看当前日期是第几个星期的方法
- javascript getBoundingClientRect() 来获取页面元素的位置的代码[修正版]第1/2页
- python通过cookie模拟已登录状态的初步研究
- Objective-C中常用的结构体NSRange,NSPoint,NSSize(CGSize),NSRect实例分析
- 密码绑定至密码文本框中(TextMode设为Password)
- JS解决IOS中拍照图片预览旋转90度BUG的问题
- JS实现文字链接感应鼠标淡入淡出改变颜色的方法
- 将数字转换成大写的人民币表达式的js函数
- 触屏中的JavaScript事件分析
- Zend Framework教程之Zend_Form组件实现表单提交并显示错误提示的方法
- 大家看了就明白了css样式中类class与标识id选择符的区别小结
- 基于jQuery实现文字打印动态效果
- SQL 实用语句
- 在VS2008中使用jQuery智能感应的方法
- js字母大小写转换实现方法总结
- C语言编写获取Linux本地目录及本机信息的小程序实例
- C和指针小结(推荐)
- VC++实现的OpenGL线性渐变色绘制操作示例
- android中ProgressDialog与ProgressBar的使用详解
- Java基于中介者模式实现多人聊天室功能示例