本文实例讲述了Python3实现的判断回文链表算法。分享给大家供大家参考，具体如下：
问题：
请判断一个链表是否为回文链表。
方案一：指针法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution: def isPalindrome(self, head): """ 判断一个链表是否是回文的，很自然的想法就是两个指针，一个指针从前往后走，一个指针从后往前走，判断元素值是否相同，这里要分几个步骤来进行求解：1、找到链表长度的一半，用追赶法，一个指针一次走两步，一个指针一次走一步2、将后一半数组转置3、判断链表是否是回文链表 :type head: ListNode :rtype: bool """ slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next node = None while slow: nxt = slow.next slow.next = node node = slow slow = nxt while node and head: if node.val != head.val: return False node = node.next head = head.next return True |
方案二：列表法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def isPalindrome(self, head): """ :type head: ListNode :rtype: bool """ res = [] cur = head while cur: res.append(cur.val) cur = cur.next return res == res[: : -1] |
希望本文所述对大家Python程序设计有所帮助。
原文链接：https://blog.csdn.net/zhenghaitian/article/details/81025147
