现给定一个链表ListNode* pHead，定义bool代表链表是否为回文，请编写程序。
测试样例：
{1,2,3,2,1} 返回：true
{1,2,3,2,3} 返回：false
[编程题]回文链表
九城城主
思路：利用快慢指针，找到中间节点；将慢指针节点的值压入栈，到达中间节点后，依次出栈与后续节点的值比较。特别注意长度奇偶数。
代码如下：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class Palindrome {
public:
bool isPalindrome(ListNode* pHead) {
// write code here
if(pHead == NULL)
return true;
stack<int> ss;
ListNode* p = pHead;
ListNode* q = pHead;
ss.push(p->val);
while(q->next != NULL &&
q->next->next != NULL)
{
p = p->next;
ss.push(p->val);
q = q->next->next;
}
if(q->next ==
NULL) //长度为奇数
ss.pop();
p = p->next;
while(!ss.empty())
{
if(ss.top() != p->val)
break;
p = p->next;
ss.pop();
}
if(ss.empty())
return true;
else
return false;
}
};
编辑于 2015-08-18 20:51:02
回复(22)
全部入栈：依次比较（若是回文，出栈顺序链表顺序一定相同）
public class Palindrome {
public boolean isPalindrome(ListNode pHead) {
if (pHead == null || pHead.next == null) return false;
ListNode currentNode = pHead;
Stack<Integer> stack = new Stack<Integer>();
while (currentNode != null) {
stack.push(currentNode.val);
currentNode = currentNode.next;
}
while (pHead != null) {
if (stack.pop() != pHead.val) {
return false;
}
pHead = pHead.next;
}
return true;
}
}
发表于 2020-08-25 14:32:41
回复(0)
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Palindrome {
public boolean isPalindrome(ListNode pHead) {
// write code here
if(pHead == null || pHead.next == null){
return true;
}
List<Integer> list = new ArrayList<>();
ListNode p = pHead; //遍历链表，将结点值存入 list
while(p != null){
list.add(p.val);
p = p.next;
}
int i = 0,j = list.size() - 1;
//从两头开始遍历比较元素值，不相等则返回false
while(i <= j){
if(list.get(i) != list.get(j)){
return false;
}
i++;
j--;
}
return true;
}
}
编辑于 2020-04-09 09:27:21
回复(0)
public class Palindrome {
public boolean isPalindrome(ListNode pHead) {
if(pHead == null)
return false;
ListNode p = pHead;
ArrayList<Integer> list = new ArrayList<>();
while(p != null){
list.add(p.val);
p = p.next;
}
for(int i = 0, j = list.size() - 1; i < j ;i++, j--){
if(list.get(i) != list.get(j))
return false;
}
return true;
}
}
发表于 2019-12-10 16:48:42
回复(0)
利用两个栈存放节点值就可，运行时间稳定在35ms左右，占用空间在9950K左右
public boolean isPalindrome(ListNode pHead)
{
if(pHead==null||pHead.next==null)
return false;
else
{
// 创建两个栈
Stack<Integer>L1=new Stack<>();
Stack<Integer>L2=new Stack<>();
//将所有节点值依次入栈
while(pHead!=null)
{
L1.add(pHead.val);
pHead=pHead.next;
}
int count=L1.size()/2;
int k=L1.size()%2;
//将L1中一半的值放进L2中，例如开始L1为{1,2,3,2,1}， L2为空
//执行此循环后L1为{1,2,3}, L2为{1，2}
while(count>0)
{
L2.add(L1.pop());
count--;
}
//判断链表的节点数是奇数还是偶数，如果是偶数
//那么L1现在的顶就是这个中间的数，把它从L1中pop掉
if(k!=0) {L1.pop();}
return L1.equals(L2)?true:false;//比较是否相同，然后返回结果
}
}
编辑于 2019-08-10 19:17:53
回复(0)
public boolean isPalindrome(ListNode pHead) { ListNode mid = pHead; ListNode fast = pHead; if(pHead==null||pHead.next==null){ return true; } /* mid 为中间位置的节点 如果链表长度为偶数，指前半部分的最后一个 如果链表长度为奇数，指向正中间的一个 这样操作mid之后的链表就可以了 */ while(fast.next!=null){ fast=fast.next; if(fast.next!=null){ fast = fast.next; mid=mid.next; } } ListNode afertReserveHead = reserve(mid); //反转后半部分链表 ListNode frontNode=pHead; ListNode endNode=afertReserveHead; do{ if(frontNode.val!=endNode.val) { return false; } frontNode=frontNode.next; endNode=endNode.next; }while(frontNode!=mid); return true; } /** * @desc: 反转链表从pHead开始，pHead的next不发生改变(这里pHead的next无影响) * @date: 2018/9/10 16:06 * @param: * @return: 反转之后链表的表头 */ public ListNode reserve(ListNode pHead){ if(pHead==null||pHead.next==null){ return pHead; } ListNode preNode = pHead; ListNode currNode=preNode.next; while(currNode!=null){ ListNode nextNode=currNode.next; currNode.next=preNode; preNode=currNode; currNode=nextNode; } return preNode; }
发表于 2018-09-10 16:50:13
回复(0)
//钻系统的漏洞
public class Palindrome {
public boolean isPalindrome(ListNode pHead) {
StringBuilder sb=new StringBuilder();
while(pHead.next!=null) {
sb.append(pHead.val);
pHead=pHead.next;
}
sb.append(pHead.val);
String s1=sb.toString();
String s2=sb.reverse().toString();
if(s1.equals(s2))
return true;
return false;
}
}
发表于 2017-09-07 16:33:53
回复(0)
// java版快慢指针定中，辅助栈空间 public boolean isPalindrome(ListNode pHead) { if (pHead==null) return false; if (pHead.next==null) return true; ListNode slower = pHead; ListNode faster = pHead; Stack<ListNode> stack = new Stack<>(); boolean isOdd=true; while (faster!=null&&faster.next!=null){ stack.push( slower ); slower = slower.next; faster = faster.next.next; if(faster==null){ isOdd = false; } } // 奇数个结点，slower还要next一下 if(isOdd) slower = slower.next; while (!stack.empty()){ if (stack.pop().val!=slower.val){ return false; }else{ slower = slower.next; } } return true; }
发表于 2017-08-05 23:37:56
回复(0)
考回文，第一个想到的就是栈，这里偷点懒，直接将链表中的元素倒进来，直接做比较咯
package com.xiroy.test;
import java.util.Stack;
public class NameList {
public boolean isPalindrome(ListNode pHead) {
//定义一个泛型为Integer的栈
//遍历链表，将结点里的数据取出来放到栈里
//遍历链表，将取出来的值跟栈顶的值一个个比较
Stack<Integer> stack = new Stack<Integer>();
ListNode current = pHead;
while(current!=null){
stack.push(current.val);
current = current.next;
}
while(pHead!=null){
int top = stack.pop().intValue();
if(top!=pHead.val){
return false;
}
pHead = pHead.next;
}
return true;
}
}
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
发表于 2017-08-01 22:47:50
回复(0)
public class Palindrome {
public boolean isPalindrome(ListNode pHead) {
// write code here
if(pHead == null){
return false;
}
Stack s = new Stack();
ListNode cur = pHead;
while(cur!=null){
s.push(cur.val);
cur = cur.next;
}
cur = pHead;
while(!s.empty()){
Object a = s.pop();
if(!a.equals(cur.val)){
return false;
}
cur = cur.next;
}
return true;
}
}
发表于 2017-06-23 15:17:46
回复(0)
获取链表的回文字符串，然后反转reverse之后还equals的话，那就是回文。
public class Palindrome {
public boolean isPalindrome(ListNode pHead) {
// write code here
ListNode p=pHead;
StringBuilder re=new StringBuilder();
while(p!=null){
re=re.append(p.val);
p=p.next;
}
String str=re.toString();
String res=re.reverse().toString();
System.out.println(re.toString());
if(res.equals(str)){
return true;
}
return false;
}
}
发表于 2017-06-09 15:37:26
回复(0)
//借用ArrayList
public boolean isPalindrome(ListNode pHead) {
if(pHead==null) return false;
ArrayList<Integer> nodeList=new ArrayList<Integer>();
while(pHead!=null){
nodeList.add(pHead.val);
pHead=pHead.next;
}
for(int i=0;i<nodeList.size()>>1;i++) if(nodeList.get(i)!=nodeList.get(nodeList.size()-1-i)) return false;
return true;
}
发表于 2017-05-11 22:22:02
回复(0)
public class Palindrome {
public boolean isPalindrome(ListNode pHead) {
// write code here
StringBuffer sb1 = new StringBuffer();
while(pHead != null) {
sb1.append(pHead.val);
pHead = pHead.next;
}
String str1 = sb1.toString();
String str2 = sb1.reverse().toString();
if(str1.equals(str2)) {
return true;
}
return false;
}
}
不知道这个是不是简单易懂
发表于 2017-05-08 16:57:31
回复(2)
public class Palindrome {
public boolean isPalindrome(ListNode pHead)
{
Stack<Integer> s=new Stack();
int[] num=new int[1000];
int count=0;
while(pHead!=null)
{
s.push(pHead.val);
num[count]=pHead.val;
pHead=pHead.next;
count++;
}
count--;
for(int i=0;i<count/2;i++)
{
if(s.pop().intValue()!=num[i])
return false;
}
return true;
}
}
发表于 2017-04-19 12:32:03
回复(0)
全部压栈然后取出和原来的链表进行比较
public class Palindrome { public boolean isPalindrome(ListNode pHead) { ListNode p=pHead; Stack<ListNode> ss=new Stack<ListNode>(); while(p!=null){ ss.push(p); p=p.next; } p=pHead; while(p!=null){ if(ss.pop().val!=p.val){ return false; } p=p.next; } return true; } }
编辑于 2017-04-05 10:36:31
回复(0)
public static boolean isPalindrome(ListNode pHead) {
List<Integer> list =new
ArrayList<Integer>();
while(pHead!=null){
//用 list 保存节点数据
list.add(pHead.val);
pHead=pHead.next;
}
int i=0 ;// 头
int j=list.size()-1; // 尾
while(i<j){
// 两边往中间扫， 如果不想等 直接返回 false
if(list.get(i) != list.get(j))
return false;
i++;j--;
}
return true;
}
编辑于 2017-03-26 20:02:45
回复(0)
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Palindrome {
public boolean isPalindrome(ListNode pHead) {
if (pHead == null) return false;
if (pHead.next == null) return true;
ArrayList<Integer> list = new ArrayList<>();
while (pHead != null) {
list.add(pHead.val);
pHead = pHead.next;
}
boolean notEqueal = false;
for (int i = 0; i < list.size(); i ++) {
if (list.get(i) != list.get(list.size() - 1 - i)) {
notEqueal = true;
}
}
return !notEqueal;
}
}
发表于 2017-03-15 17:17:18
回复(0)
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Palindrome {
public boolean isPalindrome(ListNode pHead) {
// write code here
String str = "";
String str2 = "";
while(pHead!=null){
str = str+String.valueOf(pHead.val);
str2 = String.valueOf(pHead.val)+str2;
pHead = pHead.next;
}
if(str.equals(str2)){
return true;
}else{
return false;
}
}
}
发表于 2016-09-29 15:20:08
回复(2)
思路：链表压栈（反转），并记录长度；对比前一半与后一半（出栈 ）是否相同，不同则返回false。
public class Palindrome {
public boolean isPalindrome(ListNode pHead) {
// write code here
if(pHead==null) return true;
Stack<ListNode> stack = new Stack<>();
ListNode p = pHead;
int length=0,index=1;
while(p!=null){
stack.push(p);
p=p.next;
length++;
}
p = pHead;
while(p!=null && index<=length/2){
if(p.val!=stack.pop().val) return false;
p = p.next;
index++;
}
return true;
}
}
编辑于 2016-09-02 16:19:31
回复(0)
public class Palindrome {
public boolean isPalindrome(ListNode pHead) {
// write code here
if(pHead==null) return false;
ArrayList<Integer> rm=new ArrayList<Integer>();
while(pHead!=null)
{
rm.add(pHead.val);
pHead=pHead.next;
}
int l=rm.size()-1;
int f=0;
while(true)
{
if(l==f||l-f==1) return true;
if(rm.get(f)!=rm.get(l)) return false;
if(rm.get(f)==rm.get(l))
{
l--;
f++;
}
}
}
}
发表于 2016-09-01 18:08:13
回复(0)
问题信息
难度：
20条回答
170收藏
46312浏览
通过挑战的用户
查看代码-
2023-03-11 10:49:13
-
2023-02-13 18:03:47 -
2022-09-13 17:27:09 -
2022-09-11 12:16:48 -
2022-09-10 20:54:13
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
