我要招人

去企业版

首页 > 试题广场 >

回文链表

[编程题]回文链表

热度指数：29263 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

现给定一个链表ListNode* pHead，定义bool代表链表是否为回文，请编写程序。

测试样例：

{1,2,3,2,1}

返回：true

{1,2,3,2,3}

返回：false

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

推荐

九城城主

思路：利用快慢指针，找到中间节点；将慢指针节点的值压入栈，到达中间节点后，依次出栈与后续节点的值比较。特别注意长度奇偶数。

代码如下：

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)

Python

cap_liu201910152039525

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Palindrome:
    def isPalindrome(self, pHead):
        # write code here
        p = pHead
        flag = False
        valList = []
        while p != None:
            valList.append(p.val)
            p = p.next
        for i in range(0,len(valList)):
            if valList[i] == valList[0-(i+1)]:
                flag = True
            else:
                flag = False
                break
        return flag

发表于 2019-10-23 22:28:50 回复(0)

Python

华科平凡

PYthon solution,easy to understand

class Palindrome:
    def isPalindrome(self, pHead):
        # write code here
        arr=[]
        while pHead:
            arr.append(pHead.val)
            pHead=pHead.next
        return arr==arr[::-1]

发表于 2017-10-01 20:24:51 回复(2)

Python

Yannyezixin

思路：

利用一个快指针，慢指针。慢指针每次走一步，快指针每次走两步。把慢指针走过的结点入栈

比较栈中结点跟慢指针剩余为走过的结点（特别注意链表长度是奇数还是偶数，如果是奇数，慢指针应该跳过中间结点再进行比较）

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Palindrome:
    def isPalindrome(self, pHead):
        if not pHead or not pHead.next:
            return False
        
        stack = []
        slow = pHead
        fast = pHead.next
        
        stack.append(slow.val)
        while True:
            # 链表是偶数长度
            if not fast.next:
                mid = slow.next
               	break
            elif fast.next and not fast.next.next:
                mid = slow.next.next
                break
            slow = slow.next
            fast = fast.next.next
            stack.append(slow.val)
        
        while stack and mid:
            top = stack.pop()
            if top != mid.val:
                return False
            mid = mid.next
       	return True

发表于 2016-08-02 10:53:45 回复(0)