写一个算法,实现两个长度不等的单链表操作,要求把短的单链表追加到长的单链表之后。
时间: 2023-05-18 16:04:22 浏览: 36
以下是实现该算法的 Python 代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def append_lists(l1: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1
# 计算两个链表的长度
len1, len2 = 0, 0
p1, p2 = l1, l2
while p1:
len1 += 1
p1 = p1.next
while p2:
len2 += 1
p2 = p2.next
# 把短的链表追加到长的链表之后
if len1 > len2:
p1, p2 = l1, l2
else:
p1, p2 = l2, l1
for _ in range(abs(len1 - len2)):
p1 = p1.next
while p2:
p1.val += p2.val
p1 = p1.next
p2 = p2.next
# 处理进位
p = l1 if len1 > len2 else l2
while p:
if p.val >= 10:
p.val -= 10
if not p.next:
p.next = ListNode(1)
else:
p.next.val += 1
p = p.next
# 返回结果
return l1 if len1 > len2 else l2
```
该算法的时间复杂度为 O(max(m, n)),其中 m 和 n 分别为两个链表的长度。