首页 > 试题广场 >

判断一个链表是否为回文结构

[编程题]判断一个链表是否为回文结构
  • 热度指数：185965 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个链表，请判断该链表是否为回文结构。
回文是指该字符串正序逆序完全一致。
数据范围： 链表节点数 ，链表中每个节点的值满足
示例1

输入

{1}

输出

true
示例2

输入

{2,1}

输出

false

说明

2->1
示例3

输入

{1,2,2,1}

输出

true

说明

1->2->2->1

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
Python
牛客362242806号头像 牛客362242806号
class Solution:
    def isPail(self , head ):
        # write code here
        list=[]
        while head:
            list.append(head.val)
            head=head.next
        i=0
        j=len(list)-1
        while i<=j:
            if list[i]==list[j]:
                i+=1
                j-=1
            else:
                return False
        return True
发表于 2022-07-07 15:41:19 回复(0)
Python
wengJJ头像 wengJJ
Python
两种做法
一种利用数组存储值进行判断
第二种利用快慢指针找到中点，分割成两条链，在进行值判断 
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param head ListNode类 the head
# @return bool布尔型
#
class Solution:
    def isPail(self , head ):
        # write code here
#         节点值比较方法
#         if not head:
#             return True
#         stack = []
#         cur = head 
#         while cur:
#             stack.append(cur.val)
#             cur = cur.next
#         return stack == stack[::-1]  
#         快慢指针找中点
        if not head&nbs***bsp;not head.next:
            return True
        slow = head
        fast = head
        while fast and fast.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next
#         从中点断开 分成两条链 head and slow
        pre.next = None
#         链表反转
        head2 = None
        while slow:
            temp = slow.next
            slow.next = head2
            head2 = slow
            slow = temp
        while head and head2:
            if head.val != head2.val:
                return False
            head = head.next
            head2 = head2.next
        return True


发表于 2021-04-23 14:40:00 回复(0)
Python
牛客864532994号头像 牛客864532994号
为什么python的答案中大家通过的，都没有在类里面写，在类Solution的isPail里面写，都是超时呢？？
发表于 2021-04-04 12:58:57 回复(0)
Python
wangqiang头像 wangqiang
牛客网有问题，同样代码leetcode可以通过，牛客网怎么都是超时
编辑于 2021-03-30 16:39:34 回复(0)
Python
糖❤头像 糖❤ 
#时间未通过
class Solution:
    def isPail(self , head ):
        # write code here
        rev=self.Reverse(head)
        result=self.isSame(head, rev)
        return result
    def Reverse(self, head):
        temp=newhead=head
        curr=None
        while temp:
            newhead=ListNode(temp.val)
            newhead.next=curr
            curr=newhead
            temp=temp.next
        return newhead
    def isSame(self, head1, head2):
        while head1 and head2:
            if head1.val != head2.val:
                return False
            head1=head1.next
            head2=head2.next
        return True

发表于 2021-03-21 16:59:48 回复(0)
Python
猫牛头像 猫牛 
为啥会超时呢。。。


class Solution:
    def isPail(self , head ):
        # write code here
        if not head&nbs***bsp;not head.next:
            return True
        
        left, right = self.cut(head)
        right = self.reverse(right)
        while left and right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        return True
        
    
    def cut(self, head):
        slow = fast = head
        i = 0
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            i += 1
        if i % 2 == 1:
            cut = slow
        else:
            cut = slow.next
        slow = None
        return head, cut
    
    def reverse(self, head):
        if not head&nbs***bsp;not head.next:
            return head
        
        tail = None
        while head:
            tmp = head.next
            head.next = tail
            tail = head
            head = tmp
        return tail


发表于 2021-03-12 01:29:17 回复(0)
Python
三滴水太热头像 三滴水太热
python怎么写呀 一直超时
class Solution: 
    def isPail(self , head ):
        # write code here
        temp =[]
        while head:
            temp.append(head.val)
            head = head.next  
        start,end =0,len(temp)-1
        while start < end :
            if temp[start] !=temp[end]:
                return False
            start +=1
            end -=1
        return True


发表于 2020-12-24 14:59:28 回复(3)
Python
在土耳其卖布的头像 在土耳其卖布的

我被超时打败了，有人救救我么

class Solution:
    def isPail(self , head ):
        # write code here
        p=head
        nums=[]
        while p :
           nums.append(p.val)
           p=p.next
        return nums==nums[::-1]
发表于 2020-09-20 13:33:45 回复(0)
Python
324134134143428头像 324134134143428
为什么逆序，然后比较不能ac？有哪里没有想到么？
发表于 2020-09-16 10:48:56 回复(13)
提交观点

问题信息

链表 双指针
难度：
10条回答 7567浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号