对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：
1->2->2->1
返回：true
[编程题]链表的回文结构
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
//方法一:利用额外空间
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
ListNode p = A; //指向表头
int len = 0; //记录表长
while(p != null){
len ++;
p = p.next;
}
//定义一个长度相同数组保存链表的数据
int[] a = new int[len];
for(int i=0; i<len; i++){
a[i] = A.val;
A = A.next;
}
//转化为判断数组回文
for(int i=0; i<len/2; i++){
if(a[i] != a[len-1-i]){
return false;
}
}
return true;
}
}
//方法二:由于不允许利用额外空间,先找到中间结点,再把中间结点后的链表逆置,再依次比较结点是否相等
import java.util.*;
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
ListNode fast = A; //都指向头结点
ListNode slow = A;
//找mid结点
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
ListNode nextMid = slow.next; //mid的下一个结点
slow.next = null; //断链
ListNode pre = null; //标记逆置后的表头
ListNode next = null;
//逆置
while(nextMid != null){
next = nextMid.next;
nextMid.next = pre;
pre = nextMid;
nextMid = next;
}
//依次比较两链表
while(A != null && pre != null){
if(A.val != pre.val){
return false;
}
A = A.next;
pre = pre.next;
}
return true;
}
}
编辑于 2017-03-20 14:11:13
回复(1)
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
// write code here
//思路： 1->2->2->1
//快慢指针找到之间结点 将后面的链表进行逆置 现在用一下CPP的方法
if(A==nullptr || A->next==nullptr)
return true;
stack<int> s;
//找之间结点
ListNode* fast = A;
ListNode* slow = A;
while(fast && fast->next)
{
s.push(slow->val);
slow = slow->next;
fast = fast->next->next;
}
//如何判断奇数偶数
if(fast)
slow = slow->next;
while(!s.empty() && slow)
{
if(s.top()!=slow->val)
{
return false;
}
s.pop();
slow = slow->next;
}
if(!s.empty() || slow)
{
return false;
}
return true;
}
};
发表于 2021-11-26 22:06:37
回复(0)
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
// write code here
if (A == NULL || A->next == NULL) return true;
ListNode* slow = A;
ListNode* fast = A;
while (fast->next && fast->next->next)
{
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
ListNode* p;
while (fast)
{
p = fast->next;
fast->next = slow;
slow = fast;
fast = p;
}
fast = A;
while (fast)
{
if (fast->val != slow->val) return false;
fast = fast->next;
slow = slow->next;
}
return true;
}
};
发表于 2019-10-12 23:53:02
回复(0)
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
// write code here
Stack<Integer> arr=new Stack<>();
ListNode B=A;
while(A!=null){
arr.push(A.val);
A=A.next;
}
while(!arr.isEmpty()){
if(arr.pop()==B.val)
B=B.next;
else
return false;
}
return true;
}
}
发表于 2018-06-28 21:07:51
回复(0)
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
// write code here
Stack<Integer> stack = new Stack<Integer>();
ListNode a = A;
while(A!=null)
{
stack.push(A.val);
A = A.next;
}
while(!stack.isEmpty())
{
if(stack.pop()!=a.val)
return false;
else{
a = a.next;
}
}
return true;
}
}
发表于 2018-03-26 17:58:10
回复(0)
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
// write code here
ListNode *fast=A,*slow=A;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
}
ListNode *tail=reverseList(slow);
ListNode *head=A;
while(tail&&head)
{
if(tail->val==head->val)
{
tail=tail->next;
head=head->next;
}
else
return false;
}
return true;
}
ListNode *reverseList(ListNode *head)
{
if(!head||!head->next)return head;
ListNode *pReverse=reverseList(head->next);
ListNode *pPrev=head->next;
pPrev->next=head;
head->next=NULL;
return pReverse;
}
};
发表于 2018-01-17 14:00:25
回复(0)
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
if(A==NULL)
return false;
else if(A->next==NULL)
return true;
ListNode *p = A;
ListNode *q = A;
while(p!=NULL && p->next!=NULL)
{
p = p->next->next; q = q->next; } ListNode *s = q->next; ListNode *t = s->next; while(s!=NULL) { s->next = q; q = s; s = t; t = t->next; } while(A!=NULL) { if(A->val != q->val) return false; else{ if(A->next != q) return true; A = A->next; q = q->next; } } return true;
}
};
发表于 2017-11-15 13:16:11
回复(0)
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
// write code here
if (A == null) {
return false;
}
if (A.next == null) {
return true;
}
ListNode slow = A;
ListNode quick = A;
while (quick != null && quick.next != null) {
quick = quick.next;
if (quick.next != null) {
quick = quick.next;
}
slow = slow.next;
}
ListNode p = slow.next;
ListNode p1 = p.next;
while (p != null) {
p.next = slow;
slow = p;
p = p1;
if (p1 != null) {
p1 = p1.next;
}
}
while (A != slow) {
if (A.val != slow.val) {
return false;
}
if (A.next == slow) {
return true;
}
A = A.next;
slow = slow.next;
}
return true;
}
}
发表于 2017-09-14 22:24:27
回复(0)
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
int len=0,mid;
ListNode *p=A,*q,*pre;
while(p){
len++;
p=p->next;
}
p=A;
mid=len/2+len%2;
while(mid){
pre=p;
p=p->next;
mid--;
}
while(p){
q=p;
p=p->next;
q->next=pre;
pre=q;
}
p=A,q=pre;
while(p!=q&&p->next!=q&&q->next!=p&&p->val==q->val){
p=p->next;
q=q->next;
}
if(p==q||(p->next==q&&q->next==p))
return true;
else
return false;
}
};
发表于 2016-09-08 21:23:48
回复(0)
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
// write code here
int count=0; //统计该链表的长度
int i=0; //数组下表
ListNode p=A;
while(p!=null){ //开始统计链表长度
count++;
p=p.next;
}
ListNode t=A;
int tmp[]=new int[count]; //定义一个长度为count的数组用于保存链表的数据
while(t!=null){
tmp[i]=t.val;
i++;
t=t.next;
}
for(int m=0;m< count/2;m++){
if(!(tmp[m]==tmp[count-m-1])){ //一旦发现有不相等的就返回false
return false;
}
}
return true;
}
}
编辑于 2016-04-16 16:47:25
回复(0)
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
// write code here
if(A == NULL) return false;
bool flag = true;
ListNode *firstNode = A;
ListNode *secondNode = A;
while(secondNode->next != NULL) {
secondNode = secondNode->next;
}
while(firstNode < secondNode) {
if(firstNode->val != secondNode->val) {
flag = false;
break;
}
firstNode = firstNode->next;
secondNode = updateSecondNode(A, secondNode);
}
return flag;
}
ListNode* updateSecondNode(ListNode *A, ListNode *secondNode) {
ListNode *preNode = A;
while(preNode->next != secondNode) {
preNode = preNode->next;
}
return preNode;
}
};
发表于 2016-04-03 18:43:01
回复(0)
本方法是利用了栈的结构，将源node从中间斩断，后半段放入栈中，通过弹栈的方式与源头开始做比对，本代码可以更简单，这样写的思路更清晰一些。
importjava.util.*;/*public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}}*/public class PalindromeList {public boolean chkPalindrome(ListNode A) {// write code hereStack<ListNode> s = newStack();int nodeLength = getNodeLength(A);int midIndex = nodeLength/2+nodeLength%2;ListNode head = A;for(inti = 0;i<nodeLength;i++){if(i>=midIndex){s.push(head);}head = head.next;}while(!s.isEmpty()){if(s.pop().val!=A.val){return false;}A = A.next;}return true;}public int getNodeLength(ListNode node){intsize = 0;while(node!=null){node = node.next;size++;}return size;}}
发表于 2017-10-20 10:30:31
回复(0)
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
classPalindromeList {
public:
bool chkPalindrome(ListNode* A) {
// write code here
//A为空时false,A为单个节点时true
if(A==NULL){
returnfalse;
}elseif(A->next==NULL){
returntrue;
}
//快慢指针找出中间节点
ListNode* quick=A;
ListNode* slow=A;
while(quick!=NULL&&quick->next!=NULL){
quick=quick->next->next;
slow=slow->next;
}
//将中间节点后的指针反转
ListNode* p=slow->next;
ListNode* p1=p->next;
while(p!=NULL){
p->next=slow;
slow=p;
p=p1;
p1=p1->next;
}
//从头、尾指针向中间遍历，判断A是否是回文
while(A!=slow){
if((A->val)!=(slow->val)){
returnfalse;
}else{
if(A->next==slow){
returntrue;
}
A=A->next;
slow=slow->next;
}
}
returntrue;
}
};
|
编辑于 2015-09-08 17:31:24
回复(3)
思路1：空间O(n) 整个链表遍历两边， 开一个栈，第一遍遍历把链表中每个元素push进栈中，这样堆中的元素的pop顺序就是链表的倒序输出；第二遍就开始pop栈中数据，每pop一个数据，就把这个数据跟链表中进行对比，如果相同继续往下走，如果不同返回false。
思路2：空间O(1)，使用快慢指针法，第一步设置一个块指针和一个慢指针，快指针一次走两步，慢指针一次走一步（慢），当快指针下一步为null的时候说明慢指针已经走了一半，这就可以找到中间节点。第二步反转中间链表后面的指针，第三部从头尾向中间扫描，对比每个元素是否相等，如果都相等，则是回文数，否则不是回文数。（下面网友易水给出了代码实现，这里不再叙述）
思路2：空间O(1)，使用快慢指针法，第一步设置一个块指针和一个慢指针，快指针一次走两步，慢指针一次走一步（慢），当快指针下一步为null的时候说明慢指针已经走了一半，这就可以找到中间节点。第二步反转中间链表后面的指针，第三部从头尾向中间扫描，对比每个元素是否相等，如果都相等，则是回文数，否则不是回文数。（下面网友易水给出了代码实现，这里不再叙述）
思路1java伪代码：
public void Palindrome(ListNode head){
Stack s = new Stack;
//第一遍
p1 = head; //用于第一遍遍历使用的指针
while(p != null){
s.push(p.val);
} //第二遍
p2 = head;
while(p != null){
if(p.val = s.pop()){
}else{
return false;
}
return true;
} }
发表于 2015-09-10 19:18:28
回复(8)
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
public class PalindromeList {
/**
* @param args
*/
Stack<Integer> stack = new Stack<Integer>();
Queue<Integer> queue = new LinkedList<Integer>();
public boolean chkPalindrome(ListNode A) {
// write code here
while(A != null){
stack.push(A.val);
queue.add(A.val);
A = A.next;
}
while(!stack.isEmpty()){
if(!stack.pop().equals(queue.poll())){
break;
}
}
if(stack.isEmpty()){
return true;
}else{
return false;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
ListNode A = new ListNode(1);
ListNode B = new ListNode(2);
ListNode C = new ListNode(2);
ListNode D = new ListNode(1);
A.next = B;
B.next = C;
C.next = D;
PalindromeList pa = new PalindromeList();
boolean p = pa.chkPalindrome(A);
System.out.println(p);
}
}
发表于 2016-03-19 19:33:27
回复(2)
先将链表反转，然后判断两个链表相应位置上的值是否相等即可。
public boolean chkPalindrome(ListNode A) {
ListNode B = reverseList(A);
while(A != null){
if(A.val != B.val){
return false;
}
A = A.next;
B = B.next;
}
return true;
}
public ListNode reverseList(ListNode head){
if(head == null){
return null;
}
//直接处理第一个节点
ListNode newHead = new ListNode(head.val);
newHead.next = null;
ListNode temp = null ;
//直接从第二个节点开始处理（从第二个节点开始的处理方式一样）
while(head.next != null){
temp = new ListNode(head.next.val);
temp.next = newHead;
newHead = temp;
head = head.next;
}
return newHead;
}
发表于 2016-04-05 10:40:20
回复(0)
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
// write code here
Stack<Integer> stack = new Stack<Integer>();
ListNode B = A;
int length = 0;
while(B!=null){
length++;
B = B.next;
}
int halfLength = length/2;
while(halfLength!=0){
stack.push(A.val);
A = A.next;
halfLength--;
}
halfLength = length/2;
while(halfLength!=0){
if(A.val!=stack.pop())
return false;
A = A.next;
halfLength--;
}
return true;
}
}
发表于 2016-06-24 00:12:51
回复(0)
//思路1：采用栈，将链表中的前一半元素压入栈中，然后依次出栈和链表后一半元素比较。注意链表长度奇数还是偶数；见下面参考代码；
//思路2，还有快慢指针方法。
class PalindromeList {
public:
bool chkPalindrome(ListNode* A)
{
// write code here
if(A == NULL || A->next==NULL) return true;
int len=Length_of_List(A);
stack<int> st;
ListNode* p=A;
for(int i=1;i<=len/2;i++)
{
st.push(p->val);
p=p->next;
}
if(len%2==1) p=p->next;
while(p!=NULL)
{
//int k=st.top();
if(st.top()!=p->val)
return false;
st.pop();
p=p->next;
}
return true;
}
int Length_of_List(ListNode* A)
{
if(A==NULL) return 0;
ListNode* p=A;
int count=0;
while(p!=NULL)
{
count++;
p=p->next;
}
return count;
}
};
发表于 2016-08-08 20:41:51
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-03-14 14:10:49 -
2023-03-12 23:41:16 -
2023-02-28 22:05:03 -
2022-12-15 21:56:41
-
2022-11-12 17:04:34
相关试题
-
评论(64) 来自常见面试题精讲（四）
-
评论(1) 来自常见面试题精讲（四）
-
评论(64) 来自常见面试题精讲（四）
-
评论(107) 来自常见面试题精讲（四）
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
