链表相减（链表之和）

## 链表相减### 简介链表相减是指对两个用链表存储的数字进行减法运算。由于链表的结构特点，无法像数组那样直接访问任意位置的元素，因此链表相减需要一些特殊处理。本文将详细介绍如何实现链表相减。### 算法思路链表相减的核心思路是

模拟人工减法运算

，从个位开始逐位相减，并处理借位情况。具体步骤如下：1.

预处理

:

确定链表长度

: 遍历两个链表，确定它们的长度。

对齐链表

: 将较短链表的头部用0填充，使其长度与较长链表一致。

判断大小

: 比较两个链表代表的数字大小，确定最终结果的正负号。2.

逐位相减

:

从个位开始，遍历两个链表。

每一位相减时，考虑前一位的借位。

若当前位不够减，则向高位借位，并将借位标记传递下去。3.

处理结果

:

去除结果链表头部多余的0。

根据预处理阶段判断的结果正负号，添加符号。### 代码实现以下代码以 Python 为例，展示链表相减的实现：```python class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef subtract_linked_lists(l1, l2):"""链表相减"""# 1. 预处理len1, len2 = get_length(l1), get_length(l2)if len1 < len2:l1, l2 = l2, l1 # 保证 l1 更长或相等l2 = pad_zero(l2, len1 - len2) # 填充 0sign = 1 if compare_lists(l1, l2) < 0: l1, l2 = l2, l1 # 保证 l1 代表的数字更大sign = -1# 2. 逐位相减dummy = ListNode(0)curr = dummyborrow = 0while l1:diff = l1.val - l2.val - borrowif diff < 0:diff += 10borrow = 1else:borrow = 0curr.next = ListNode(diff)curr = curr.nextl1 = l1.nextl2 = l2.next# 3. 处理结果result = reverse_list(dummy.next) # 反转结果链表result = remove_leading_zero(result) # 去除头部多余的 0if sign == -1:result = ListNode(-1, result) # 添加负号return resultdef get_length(head):"""获取链表长度"""count = 0while head:count += 1head = head.nextreturn countdef pad_zero(head, num):"""在链表头部填充 0"""for _ in range(num):head = ListNode(0, head)return headdef compare_lists(l1, l2):"""比较两个链表代表的数字大小"""while l1 and l2:if l1.val > l2.val:return 1elif l1.val < l2.val:return -1l1 = l1.nextl2 = l2.nextreturn 0def reverse_list(head):"""反转链表"""prev = Nonecurr = headwhile curr:next_node = curr.nextcurr.next = prevprev = currcurr = next_nodereturn prevdef remove_leading_zero(head):"""去除链表头部多余的 0"""while head and head.next and head.val == 0:head = head.nextreturn head```### 复杂度分析

时间复杂度

: O(max(m, n))，其中 m 和 n 分别为两个链表的长度。

空间复杂度

: O(max(m, n))，主要用于存储结果链表。### 总结链表相减需要仔细处理借位和链表长度问题。通过模拟人工减法的步骤，可以清晰地实现该算法。代码实现中需要注意细节，例如链表反转、去除头部多余的0等操作。

链表相减

简介链表相减是指对两个用链表存储的数字进行减法运算。由于链表的结构特点，无法像数组那样直接访问任意位置的元素，因此链表相减需要一些特殊处理。本文将详细介绍如何实现链表相减。

算法思路链表相减的核心思路是**模拟人工减法运算**，从个位开始逐位相减，并处理借位情况。具体步骤如下：1. **预处理**:* **确定链表长度**: 遍历两个链表，确定它们的长度。* **对齐链表**: 将较短链表的头部用0填充，使其长度与较长链表一致。* **判断大小**: 比较两个链表代表的数字大小，确定最终结果的正负号。2. **逐位相减**:* 从个位开始，遍历两个链表。* 每一位相减时，考虑前一位的借位。* 若当前位不够减，则向高位借位，并将借位标记传递下去。3. **处理结果**:* 去除结果链表头部多余的0。* 根据预处理阶段判断的结果正负号，添加符号。

代码实现以下代码以 Python 为例，展示链表相减的实现：```python class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef subtract_linked_lists(l1, l2):"""链表相减"""

1. 预处理len1, len2 = get_length(l1), get_length(l2)if len1 < len2:l1, l2 = l2, l1

保证 l1 更长或相等l2 = pad_zero(l2, len1 - len2)

填充 0sign = 1 if compare_lists(l1, l2) < 0: l1, l2 = l2, l1

保证 l1 代表的数字更大sign = -1

2. 逐位相减dummy = ListNode(0)curr = dummyborrow = 0while l1:diff = l1.val - l2.val - borrowif diff < 0:diff += 10borrow = 1else:borrow = 0curr.next = ListNode(diff)curr = curr.nextl1 = l1.nextl2 = l2.next

3. 处理结果result = reverse_list(dummy.next)

反转结果链表result = remove_leading_zero(result)

去除头部多余的 0if sign == -1:result = ListNode(-1, result)

添加负号return resultdef get_length(head):"""获取链表长度"""count = 0while head:count += 1head = head.nextreturn countdef pad_zero(head, num):"""在链表头部填充 0"""for _ in range(num):head = ListNode(0, head)return headdef compare_lists(l1, l2):"""比较两个链表代表的数字大小"""while l1 and l2:if l1.val > l2.val:return 1elif l1.val < l2.val:return -1l1 = l1.nextl2 = l2.nextreturn 0def reverse_list(head):"""反转链表"""prev = Nonecurr = headwhile curr:next_node = curr.nextcurr.next = prevprev = currcurr = next_nodereturn prevdef remove_leading_zero(head):"""去除链表头部多余的 0"""while head and head.next and head.val == 0:head = head.nextreturn head```

复杂度分析* **时间复杂度**: O(max(m, n))，其中 m 和 n 分别为两个链表的长度。 * **空间复杂度**: O(max(m, n))，主要用于存储结果链表。

总结链表相减需要仔细处理借位和链表长度问题。通过模拟人工减法的步骤，可以清晰地实现该算法。代码实现中需要注意细节，例如链表反转、去除头部多余的0等操作。