Python程序检查两个链表是否相同

在Python中，链表是一种非常常见的数据结构。在使用链表时，我们可能需要判断两个链表是否相同。判断两个链表是否相同的方法有多种，本文将介绍其中两种方法。

方法一：逐个比较节点

首先，我们定义一个链表节点类，将节点的值以及指向下一个节点的指针作为其属性。

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

接下来，我们定义一个函数，该函数接收两个链表的头节点作为参数，并逐个比较这两个链表的节点。如果节点的值相同且下一个节点也相同，则这两个链表是相同的。

def isSameList(head1: ListNode, head2: ListNode) -> bool:
    while head1 and head2: # 两个链表都不为空时，循环比较节点
        if head1.val != head2.val: 
            # 如果节点值不相同，则两个链表不同
            return False
        head1 = head1.next # 遍历链表1
        head2 = head2.next # 遍历链表2
    # 当其中一个链表为空时，另一个链表也为空则两个链表相同
    return not (head1 or head2)

接下来，我们定义两个链表，并调用isSameList函数来比较这两个链表是否相同。

# 创建链表1: 1 -> 2 -> 3 -> 4 -> 5
list1 = ListNode(1)
list1.next = ListNode(2)
list1.next.next = ListNode(3)
list1.next.next.next = ListNode(4)
list1.next.next.next.next = ListNode(5)

# 创建链表2: 1 -> 2 -> 3 -> 4 -> 5
list2 = ListNode(1)
list2.next = ListNode(2)
list2.next.next = ListNode(3)
list2.next.next.next = ListNode(4)
list2.next.next.next.next = ListNode(5)

print(isSameList(list1, list2)) # True

输出结果为True，表示这两个链表是相同的。

方法二：将链表转换为列表

另一种判断两个链表是否相同的方法是将链表转换为列表，然后判断这两个列表是否相同。这种方法比较简单直观。

首先，我们定义一个函数，该函数接收一个链表的头节点作为参数，并将该链表转换为列表。

def toList(head: ListNode) -> List[int]:
    res = []
    while head:
        res.append(head.val)
        head = head.next
    return res

接下来，我们可以使用刚才定义的toList函数来将链表转换为列表。然后，我们可以使用Python内置的==运算符来比较这两个列表是否相同。

# 创建链表1: 1 -> 2 -> 3 -> 4 -> 5
list1 = ListNode(1)
list1.next = ListNode(2)
list1.next.next = ListNode(3)
list1.next.next.next = ListNode(4)
list1.next.next.next.next = ListNode(5)

# 创建链表2: 1 -> 2 -> 3 -> 4 -> 5
list2 = ListNode(1)
list2.next = ListNode(2)
list2.next.next = ListNode(3)
list2.next.next.next = ListNode(4)
list2.next.next.next.next = ListNode(5)

print(toList(list1) == toList(list2)) # True

输出结果为True，表示这两个链表是相同的。