【程序员金典】回文链表

2024-02-13 03:32
文章标签 链表 程序员 回文 金典

本文主要是介绍【程序员金典】回文链表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述
请编写一个函数,检查链表是否为回文。
给定一个链表ListNode* pHead,请返回一个bool,代表链表是否为回文。
测试样例:
{1,2,3,2,1}
返回:true
{1,2,3,2,3}
返回:false

c++代码

方法一:
链表前半部分入栈,后半部分与栈中的元素比较

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class Palindrome {
public:bool isPalindrome(ListNode* pHead) {// write code here//快慢指针找到链表的中间节点stack<int> tmp;ListNode* slow=pHead,*fast=pHead;while(fast!=nullptr&&fast->next!=nullptr){tmp.push(slow->val);slow=slow->next;fast=fast->next->next;}if(fast!=nullptr)//奇数个slow=slow->next;while(slow!=nullptr){if(tmp.top()!=slow->val)return false;elsetmp.pop();slow=slow->next;}return true;}
};
方法二:

反转链表,其实只需要找到链表的中点,然后将中点后面的部分反转。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool isPalindrome(ListNode* head) {if(head==NULL||head->next==NULL)return true;//取中点的位置,后半段进行反转,然后再比较ListNode *slow=head,*fast=head;//采用快慢指针找到中点的位置,slow每次前进一步,fast每次前进两步,当fast不能再往前走的时候,slow正好到前半段的//最后一个位置while(fast->next&&fast->next->next){slow=slow->next;fast=fast->next->next;}slow->next = reverseList(slow->next);slow = slow->next;while(slow != NULL){if(head->val != slow->val)return false;head = head->next;slow = slow->next;}return true;
}ListNode* reverseList(ListNode *head)
{ListNode *pre = NULL;ListNode *next = NULL;while(head != NULL){next = head->next;head->next = pre;pre = head;head = next;}return pre;
}
};

这篇关于【程序员金典】回文链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/704371

相关文章

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法:解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一:将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定

csu1328(近似回文串)

题意:求近似回文串的最大长度,串长度为1000。 解题思路:以某点为中心,向左右两边扩展,注意奇偶分开讨论,暴力解即可。时间复杂度O(n^2); 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>#include<string>#inclu

csu1329(双向链表)

题意:给n个盒子,编号为1到n,四个操作:1、将x盒子移到y的左边;2、将x盒子移到y的右边;3、交换x和y盒子的位置;4、将所有的盒子反过来放。 思路分析:用双向链表解决。每个操作的时间复杂度为O(1),用数组来模拟链表,下面的代码是参考刘老师的标程写的。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-

建立升序链表

题目1181:遍历链表 时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:2744 解决:1186 题目描述: 建立一个升序链表并遍历输出。 输入: 输入的每个案例中第一行包括1个整数:n(1<=n<=1000),接下来的一行包括n个整数。 输出: 可能有多组测试数据,对于每组数据, 将n个整数建立升序链表,之后遍历链表并输出。 样例输

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图

LabVIEW程序员是怎样成长为大佬

成为一名LabVIEW编程领域的“大佬”需要时间、实践、学习和解决复杂问题的经验。尽管LabVIEW作为一种图形化编程语言在初期可能相对容易上手,但要真正成为精通者,需要在多个层面上深入理解。以下是LabVIEW程序员如何逐步成长为“大佬”的路径: 1. 打好基础 LabVIEW的大佬们通常在初期会打下非常坚实的基础,理解LabVIEW编程的核心概念,包括: 数据流编程模型:Lab