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