本文实例讲述了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 = None
class 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