链表前后缀【Python实现】

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

class Solution:
    def mergeList(self, a: ListNode, b: ListNode) -> ListNode:
        # 1. 将链表转换为数组
        listA = []
        listB = []
        p = a
        while p:
            listA.append(p.val)
            p = p.next
        p = b
        while p:
            listB.append(p.val)
            p = p.next
        
        lenA, lenB = len(listA), len(listB)
        
        # 2. 计算公共前缀长度 preLen
        preLen = 0
        while preLen < min(lenA, lenB) and listA[preLen] == listB[preLen]:
            preLen += 1
        
        # 3. 反转数组，计算公共后缀长度 sufLen
        revA = listA[::-1]
        revB = listB[::-1]
        revSufLen = 0
        while revSufLen < min(lenA, lenB) and revA[revSufLen] == revB[revSufLen]:
            revSufLen += 1
        sufLen = revSufLen
        
        # 4. 构造新链表
        dummy = ListNode(0)
        cur = dummy
        
        # 添加公共前缀
        for i in range(preLen):
            cur.next = ListNode(listA[i])
            cur = cur.next
        
        # 添加公共后缀
        for i in range(lenA - sufLen, lenA):
            cur.next = ListNode(listA[i])
            cur = cur.next
        
        return dummy.next