给定一个链表，请判断该链表是否为回文结构。
回文是指该字符串正序逆序完全一致。
数据范围： 链表节点数 
，链表中每个节点的值满足 
[编程题]判断一个链表是否为回文结构
先转换成双向链表再比较也可以ac
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类 the head
* @return bool布尔型
*/
struct DListNode{
int val;
struct DListNode *next;
struct DListNode *pre;
};
bool isPail(ListNode* head) {
// write code here
DListNode* h=new DListNode();
h->val=head->val;
h->pre=NULL;
h->next=NULL;
DListNode* p=h;
DListNode* pre=NULL;
ListNode* pp=head->next;
int len=1;
while(pp)
{
p->next=new DListNode();
pre=p;
p=p->next;
p->val=pp->val;
p->pre=pre;
p->next=NULL;
len++;
pp=pp->next;
}
DListNode* tail=p;
p=h;
DListNode* p2=tail;
bool flag=true;
int count=len/2;
while(count--)
{
if(p->val!=p2->val)
{
flag=false;
break;
}
p=p->next;
p2=p2->pre;
}
return flag;
}
};
发表于 2020-10-25 19:22:20
回复(1)
存数组，直接判断数组是否回文结构，速度超过98% C++代码
class Solution {
public:
bool isPail(ListNode* head) {
int a[1000005];
ListNode* now = head;
int len = 0;
while(now != nullptr) {
a[len++] = now->val;
now = now->next;
}
for (int i=0, j=len-1; i<=j; i++, j--) {
if (a[i] != a[j]) return false;
}
return true;
}
};
发表于 2021-08-16 10:55:29
回复(3)
import java.util.*;
public class Solution {
public boolean isPail (ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode reverseList = reverse(slow);
ListNode cur1 = reverseList, cur2 = head;
while (cur1 != null) {
if (cur1.val != cur2.val) {
return false;
}
cur1 = cur1.next;
cur2 = cur2.next;
}
return true;
}
public ListNode reverse(ListNode head) {
ListNode cur = head, pre = null;
while (cur != null) {
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}
发表于 2021-01-09 09:21:46
回复(3)
Java双端队列解法：
public boolean isPail (ListNode head) {
if (head == null || head.next == null) {
return false;
}
Deque<Integer> deque = new ArrayDeque<>();
while (head != null) {
deque.addLast(head.val);
head = head.next;
}
while (deque.size() > 1) {
if (!deque.pollFirst().equals(deque.pollLast())) {
return false;
}
}
return true;
}
if (head == null || head.next == null) {
return false;
}
Deque<Integer> deque = new ArrayDeque<>();
while (head != null) {
deque.addLast(head.val);
head = head.next;
}
while (deque.size() > 1) {
if (!deque.pollFirst().equals(deque.pollLast())) {
return false;
}
}
return true;
}
发表于 2020-09-01 19:01:15
回复(6)
import java.util.*;
public class Solution {
/**
*
* @param head ListNode类 the head
* @return bool布尔型
*/
public boolean isPail (ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
Stack<Integer> stack = new Stack<>();
while(slow != null){
stack.add(slow.val);
slow = slow.next;
}
while(!stack.isEmpty()){
if(stack.pop() != head.val){
return false;
}
head = head.next;
}
return true;
}
}
发表于 2020-09-08 20:26:28
回复(4)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类 the head
* @return bool布尔型
*/
public boolean isPail (ListNode head) {
//取得链表的长度，再从中间断开，判断是不是一样的
// write code here
ArrayList<Integer> list=new ArrayList<Integer>();
ListNode cur=head;
while(cur!=null){//遍历整个链表到list，就是为了获得整个链表的长度
list.add(cur.val);
cur=cur.next;
}
boolean ans=true;
for(int i=0;i<(list.size()-1)/2;i++){
if(list.get(i)!=(int)list.get(list.size()-1-i)){//注意这里强转为int
ans=false;
break;
}
}
return ans;
}
}
发表于 2023-04-12 20:21:42
回复(2)
bool isPail(struct ListNode* head ) {
// write code here
int size=0;
struct ListNode* p=head;
while(p){
size++;
p=p->next;
}
int *arr=malloc(sizeof(int)*size);
p=head;
int i=0,j=size-1;
while(p){
arr[i]=p->val;
p=p->next;
i++;
}
i=0;
while(i<j){
if(arr[i]==arr[j]){
i++;
j--;
}
else{
return false;
}
}
return true;
}
发表于 2023-02-22 22:10:38
回复(0)
public class Solution {
/**
*
* @param head ListNode类 the head
* @return bool布尔型
*/
public boolean isPail (ListNode head) {
// write code here
if(head == null){
return false;
}
// 1: 利用回文链表正反遍历相同的特性将链表节点放入栈中
Stack<ListNode> stack = new Stack<>();
ListNode cur = head;
while(cur != null){
stack.add(cur);
cur = cur.next;
}
// 2: 从链表的头节点和栈的顶开始遍历,若每个值都相等说明是回文
cur = head;
while(cur != null){
if(cur.val != stack.pop().val){
return false;
}
cur = cur.next;
}
return true;
}
}
发表于 2022-07-24 23:17:58
回复(0)
1. 找到中点，并把链表切成两段
2. 翻转后面一段
3. 依次比较数值
class Solution: def isPail(self , head: ListNode) -> bool: if not head&nbs***bsp;not head.next: return True # write code here # 1.找到中点 fast, slow = head, head slow_pre = head while fast and fast.next: fast = fast.next.next slow_pre = slow slow = slow.next # 2.slow 会在中间靠右的地方 # [1, 2, 2, 1] => slow 右边的 2 # [1, 2, 3, 2, 1] => slow 在正中间 # 断开链表 slow_pre.next = None # 2.翻转链表 def reverse(node): prev = None while node: tmp = node.next node.next = prev prev = node node = tmp return prev slow = reverse(slow) # 因为 head 会少一些 while head: if slow.val != head.val: return False slow = slow.next head = head.next return True
发表于 2022-07-19 22:50:18
回复(0)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类 the head
* @return bool布尔型
*/
public boolean isPail (ListNode head) {
// write code here
ArrayList<ListNode> a = new ArrayList<>();
while (head != null) {
a.add(head);
head = head.next;
}
for (int i = 0, j = a.size() - 1; i < a.size() / 2; i++, j--)
if (a.get(i).val != a.get(j).val)
return false;
return true;
}
}
发表于 2022-06-18 14:01:33
回复(0)
//快慢指针找中间节点加上慢指针头插法
public boolean isPail (ListNode head) {
if (head == null || head.next == null) return true;
ListNode fast = head;
ListNode slow = head; //慢指针找中间节点
ListNode pre = null; //头插法指针
while(fast != null && fast.next != null){ //不能用|| 当fast=null fast.next会越界
ListNode temp = slow.next;
fast = fast.next.next;
slow.next = pre;
pre = slow;
slow = temp;
}
if (fast != null) slow = slow.next; //奇数个节点，就跳到下一个
while(slow != null && pre != null){
if (pre.val != slow.val) return false;
slow = slow.next;
pre = pre.next;
}
return true;
}
发表于 2022-06-15 10:17:59
回复(0)
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*
* C语言声明定义全局变量请加上static，防止重复定义
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
/**
*
* @param head ListNode类 the head
* @return bool布尔型
*/
#include <stdbool.h>
typedef struct ListNode Node;
bool isPail(struct ListNode* head ) {
// write code here
if(head == NULL || head ->next == NULL){
return true;
}
Node *p1 = head;
Node *p2 = head;
//首先找到中点，当p2->next->next为 NULL，那么此时p1刚好在中点
while(p2 != NULL && p2->next != NULL){
p2 = p2->next->next;
p1 = p1->next;
}
//快指针到尾判断,如果p2不为空，说明链表的长度是奇数个
if(p2 != NULL) {
p1 = p1->next;
}
Node *p = p1;
Node *pre = NULL;
while(p != NULL){
Node *q = p->next;
p->next = pre;
pre = p;
p = q;
}
while(pre != NULL){
if(pre->val != head->val){
return false;
}
pre = pre->next;
head = head->next;
}
return true;
}
发表于 2022-05-06 00:54:15
回复(0)
方法一：直接找到链表的后半段，然后反转比较：
import java.util.*;
public class Solution {
public boolean isPail (ListNode head) {
// 空链表或者链表只有一个节点，是回文链表
if(head == null || head.next == null)
return true;
// 使用快慢指针，找到中间的节点
ListNode slow = head, fast = head.next;
while(fast.next != null && fast.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
// 需要注意的是，如果是奇数个节点的情况，慢指针slow的next是中间节点
// 这个中间节点无论是多少，不影响回文判断，因此需要再次向后移动一个位置
ListNode secondSegHead = slow.next;
if(fast.next != null)
secondSegHead = secondSegHead.next;
// 反转链表的后半段，然后比较前半段和后半段的节点数值
// 如果出现不一致的情况，说明不是回文链表；反之则是回文链表
secondSegHead = reverse(secondSegHead);
while(secondSegHead != null){
if(head.val != secondSegHead.val)
return false;
head = head.next;
secondSegHead = secondSegHead.next;
}
return true;
}
// 反转链表
private ListNode reverse(ListNode secondSegHead){
ListNode pre = null, cur = secondSegHead, next = null;
while(cur != null){
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
} 方法二：复制原链表，然后直接反转比较： import java.util.*;
public class Solution {
public boolean isPail (ListNode head) {
// 如果为空链表，或者只有一个节点，是回文链表
if(head == null || head.next == null)
return true;
// 如果链表多于两个结点，那么复制这张链表
ListNode tmp_head = head;
ListNode dummy_node = new ListNode(0);
ListNode cur = dummy_node;
while(tmp_head != null){
ListNode node = new ListNode(tmp_head.val);
cur.next = node;
cur = node;
tmp_head = tmp_head.next;
}
// 反转原表
cur = head;
ListNode pre = null, next = cur.next;
while(cur != null){
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
// 将反转的链表和复制的链表进行逐节点对比，如果完全相同就是回文链表
// 否则，不是回文链表
cur = dummy_node.next;
while(cur != null){
if(cur.val != pre.val)
return false;
cur = cur.next;
pre = pre.next;
}
return true;
}
}
发表于 2021-11-15 12:53:02
回复(0)
bool isPail(ListNode* head) {
if(!head||!head->next) return true;
ListNode* fast=head;
ListNode* slow=head->next;
while(fast->next&&fast->next->next)
{
fast=fast->next->next;
slow=slow->next;
}
//此时p在右半段链表的第一个位置
ListNode* pre=nullptr;
ListNode* next=nullptr;
while(slow)
{
next=slow->next;
slow->next=pre;
pre=slow;
slow=next;
}
while(head&&pre)
{
if(head->val!=pre->val)
return false;
head=head->next;
pre=pre->next;
}
return true;
}
发表于 2021-09-04 22:09:16
回复(0)
判断回文结构，即判断后半部分翻转后与前半部分相同，
这里有两种情况，
①链表结点数为奇数，这种情况前半段会比后半段多一个结点
②链表结点数为偶数，这种情况前半段与后半段结点数相同
首先获取后半段链表可以使用双指针的方法，慢指针一次走一个结点，快结点走两个结点，当快结点走不了(fast.next != null && fast.next.next != null)时，即可获取到后半段链表，翻转后半段链表后，遍历翻转后的后半段链表，与前半段链表一个个比对结点的值（不受①②情况影响），都相同则为回文结构，否则为非回文结构
public boolean isPail(ListNode head) {
if (head == null) {
return false;
}
ListNode fast = head;
ListNode slow = head;
// 双指针获取后半段链表
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// 获取后半段链表的翻转链表
ListNode lastHalfList = reverseList(slow.next);
// 遍历后半段链表，与前半段相比，每个结点都相等，则为回文结构
while (lastHalfList != null) {
if (lastHalfList.val != head.val) {
return false;
}
lastHalfList = lastHalfList.next;
head = head.next;
}
return true;
}
// 翻转链表
public ListNode reverseList(ListNode head) {
ListNode temp = null;
ListNode reversedList = null;
while (head != null) {
temp = head.next;
head.next = reversedList;
reversedList = head;
head = temp;
}
return reversedList;
}
发表于 2021-08-25 17:25:29
回复(0)
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类 the head
* @return bool布尔型
* 使用字符串辅助，快速判断链表是否是回文结构
*/
bool isPail(ListNode* head) {
if (head == NULL) {
return true;
}
string s = "";
while(head) {
s += (head->val + '0');
head = head->next;
}
int i = 0;
int j = s.size() - 1;
while(i < j) {
if (s[i++] != s[j--]) {
return false;
}
}
return true;
}
};
发表于 2021-02-17 22:22:07
回复(1)
struct ListNode* reserve(struct ListNode** phead)
{
struct ListNode*head=*phead;
struct ListNode*nest=head->next;
head->next=NULL;
while(nest->next)
{
struct ListNode*nnest=nest->next;
nest->next=head;
head=nest;
nest=nnest;
}
nest->next=head;
return nest;
}
bool isPail(struct ListNode* head ) {
struct ListNode* phead=head;
int len = 0;
while(phead)
{
phead = phead->next;
len++;
}
if(len==1)
{
return true;
}
len = len/2;
struct ListNode* pphead=head;
while(len)
{
len--;
pphead=pphead->next;
}
struct ListNode* cur= reserve(&pphead);
while(cur)
{
if((cur->val)!=(head->val))
{
return false;
}
cur = cur->next;
head=head->next;
}
return true;
}
发表于 2024-03-03 10:39:53
回复(1)
问题信息
难度：
343条回答
540收藏
7508浏览
通过挑战的用户
查看代码-
2023-03-13 10:58:26
-
2023-03-12 12:59:31
-
2023-03-01 16:03:58
-
2023-02-25 17:20:23
-
2023-02-24 16:34:26
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
