检查单链表是否为回文的Python程序

更多Python相关文章，请阅读：Python 教程

什么是回文

回文是指正着读和反着读都一样的字符串或数列，例如：racecar、level、12321等。

单链表的定义

单链表是由一系列节点组成的数据结构，每个节点包含元素和指向下一个节点的指针。单链表的最后一个节点指向None。

以下代码是Python语言中单链表的定义：

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None

如何判断一个单链表是否为回文

判断一个单链表是否为回文的方法是将单链表中的每个节点的元素值放入一个数组中，然后对这个数组进行判断。

判断数组是否为回文的方法是从数组的两端开始向中间靠近，每次比较两端的元素是否相同，如果不同则该数组不是回文。如果一直比较到中间都相同，则该数组是回文。

以下代码是Python语言中判断单链表是否为回文的程序：

def isPalindrome(head):
    vals = []
    while head:
        vals.append(head.val)
        head = head.next
    return vals == vals[::-1]

上述代码中，变量vals是一个数组，它用来存储单链表中的元素值。在单链表的每个节点中，元素值存储在val属性中。

代码中的while循环用来遍历单链表中的所有节点，每次将节点的元素值放入vals数组中。当head变量指向None时，循环结束。

最后，代码比较vals数组和它的反转数组vals[::-1]是否相同，以判断单链表是否为回文。如果相同则返回True，否则返回False。

测试程序

为了测试上述程序的正确性，我们可以编写一个单元测试程序。以下是单元测试程序的代码：

def test_isPalindrome():
    llist1 = LinkedList()
    llist1.head = Node(1, Node(2, Node(2, Node(1))))
    assert isPalindrome(llist1.head) == True

    llist2 = LinkedList()
    llist2.head = Node(1, Node(2, Node(3, Node(2, Node(1)))))
    assert isPalindrome(llist2.head) == True

    llist3 = LinkedList()
    llist3.head = Node(1, Node(2, Node(3, Node(4, Node(1)))))
    assert isPalindrome(llist3.head) == False

    llist4 = LinkedList()
    llist4.head = Node(1, Node(2, Node(3, Node(1))))
    assert isPalindrome(llist4.head) == False

    print("All test cases pass")

上述代码中，我们创建了四个单链表，分别为：