当前位置:脚本大全 > > 正文

怎么用python实现链表(Python3实现的判断回文链表算法示例)

时间:2022-01-14 02:32:19类别:脚本大全

怎么用python实现链表

Python3实现的判断回文链表算法示例

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

    上一篇下一篇

    猜您喜欢

    热门推荐