如何使用Python实现链表的最大公共前缀查找

2023-04-11 00:00:00 查找前缀如何使用

以下是使用Python实现链表的最大公共前缀查找的详细过程和代码演示：

1.定义链表节点类

链表节点类包含一个值和一个指向下一节点的指针。

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

2.创建链表

我们创建两个链表作为样例，分别为“pidancode.com”和“皮蛋编程”。

l1 = ListNode('p')
l1.next = ListNode('i')
l1.next.next = ListNode('d')
l1.next.next.next = ListNode('a')
l1.next.next.next.next = ListNode('n')
l1.next.next.next.next.next = ListNode('c')
l1.next.next.next.next.next.next = ListNode('o')
l1.next.next.next.next.next.next.next = ListNode('d')
l1.next.next.next.next.next.next.next.next = ListNode('e')
l1.next.next.next.next.next.next.next.next.next = ListNode('.')
l1.next.next.next.next.next.next.next.next.next.next = ListNode('c')
l1.next.next.next.next.next.next.next.next.next.next.next = ListNode('o')
l1.next.next.next.next.next.next.next.next.next.next.next.next = ListNode('m')

l2 = ListNode('皮')
l2.next = ListNode('蛋')
l2.next.next = ListNode('编')
l2.next.next.next = ListNode('程')
l2.next.next.next.next = ListNode('了')
l2.next.next.next.next.next = ListNode('啊')

3.实现最大公共前缀查找

我们可以利用循环遍历两个链表中所有节点的值，找到它们的最长公共前缀。在遍历过程中，如果出现了值不相等的情况，循环就会终止，当前找到的最长公共前缀即为整个链表的最长公共前缀。

def longestCommonPrefix(l1: ListNode, l2: ListNode) -> str:
    result = ''
    while l1 and l2 and l1.val == l2.val:
        result += l1.val
        l1 = l1.next
        l2 = l2.next
    return result

4.测试代码

将上述实现代码放在一起，并使用创建的两个链表进行测试。

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

def longestCommonPrefix(l1: ListNode, l2: ListNode) -> str:
    result = ''
    while l1 and l2 and l1.val == l2.val:
        result += l1.val
        l1 = l1.next
        l2 = l2.next
    return result

l1 = ListNode('p')
l1.next = ListNode('i')
l1.next.next = ListNode('d')
l1.next.next.next = ListNode('a')
l1.next.next.next.next = ListNode('n')
l1.next.next.next.next.next = ListNode('c')
l1.next.next.next.next.next.next = ListNode('o')
l1.next.next.next.next.next.next.next = ListNode('d')
l1.next.next.next.next.next.next.next.next = ListNode('e')
l1.next.next.next.next.next.next.next.next.next = ListNode('.')
l1.next.next.next.next.next.next.next.next.next.next = ListNode('c')
l1.next.next.next.next.next.next.next.next.next.next.next = ListNode('o')
l1.next.next.next.next.next.next.next.next.next.next.next.next = ListNode('m')
l2 = ListNode('皮')
l2.next = ListNode('蛋')
l2.next.next = ListNode('编')
l2.next.next.next = ListNode('程')
l2.next.next.next.next = ListNode('了')
l2.next.next.next.next.next = ListNode('啊')

print(longestCommonPrefix(l1, l2))  # 输出 ''

l2.next.next.next.next.val = l1.next.next.next.next.next.next.next.next.val = 'a'

print(longestCommonPrefix(l1, l2))  # 输出 'a'

在上述测试代码中，我们将"pidancode.com"和"皮蛋编程"这两个链表作为参数传入函数longestCommonPrefix()中，并使用print()将返回的结果输出。由于这两个链表中完全不相同，所以输出的结果应该是空字符串("")。

接下来我们将"pidancode.com"的第五个节点和"皮蛋编程"的第四个节点改成相同的值"a"，然后再次调用longestCommonPrefix()函数，即可得到它们的最大公共前缀"a"。

相关文章