Python中链表的链表元素相减（Subtract）操作

2023-04-11 00:00:00 操作元素链表

链表的链表元素相减（Subtract）操作是指将两个链表中对应位置的元素相减，将结果保存到新的链表中。如果两个链表长度不同，则以较短链表的长度为准。

下面是Python实现链表的链表元素相减操作的代码示例：

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

class Solution:
    def subtract(self, list1: ListNode, list2: ListNode) -> ListNode:
        # 链表长度不足时在高位补0
        len1, len2 = self.getLength(list1), self.getLength(list2)
        if len1 < len2:
            list1 = self.padZeros(list1, len2 - len1)
        else:
            list2 = self.padZeros(list2, len1 - len2)

        # 对应位元素相减
        new_head = ListNode(0)
        p, q, cur = list1, list2, new_head
        while p:
            cur.next = ListNode(p.val - q.val)
            cur, p, q = cur.next, p.next, q.next

        # 删除高位多余的0
        while new_head.next and new_head.next.val == 0:
            new_head.next = new_head.next.next
        return new_head.next

    def getLength(self, head: ListNode) -> int:
        length = 0
        while head:
            length += 1
            head = head.next
        return length

    def padZeros(self, head: ListNode, num_zeros: int) -> ListNode:
        new_head = ListNode(0)
        new_head.next = head
        for i in range(num_zeros):
            head = new_head.next
            new_head.next = ListNode(0)
            new_head.next.next = head
        return new_head.next

在上述代码中，我们首先遍历两个链表，并根据长度差异，在短链表高位补0，使得两个链表长度相同。然后对应位元素相减，将结果保存到新的链表中。最后删除高位多余的0，返回新的链表。

下面是一个实际例子，演示如何对两个链表进行相减操作：

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

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

# 执行相减操作
s = Solution()
new_head = s.subtract(head1, head2)

# 输出结果链表：-4 -> -2 -> 0 -> 2 -> 4
while new_head:
    print(new_head.val, end=' -> ')
    new_head = new_head.next

运行上述代码，输出结果为：

-4 -> -2 -> 0 -> 2 -> 4 ->

这说明链表1与链表2每个位置上的元素相减，得到的新链表对应元素为-4、-2、0、2、4。

相关文章