题目内容:已知单链表LA=(a1,a2,…,am)和LB=(b1,b2,…,bn),编写程序按以下规则将它们合并成一个单链表LC,要求新表 LC利用原表的存储空间。 LC=(a1,b1,…,am,bm,bm+1,…,bn),m<=n 或者 LC=(a1,b1,…,an,bn,an+1,…,am),m>n 输入格式:一行内输入单链表LA中的数据(若干个正整数,之间用空格隔开,并以-1结束) 一行内输入单链表LB的数据(若干个正整数,之间用空格隔开,并以-1结束) 输出格式:一行内输出合并后单链表LC的数据结果,之间用两个分隔符 -- 隔开,结束标志-1不输出。 输入样例:1 3 5 7 -1 2 4 6 -1 输出样例:--1--2--3--4--5--6--7 时间限制:500ms内存限制:32000kb
时间: 2024-02-25 21:59:31 浏览: 103
以下是实现该算法的Python代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_linked_lists(head1: ListNode, head2: ListNode) -> ListNode:
dummy = ListNode()
tail = dummy
while head1 and head2:
tail.next = head1
head1 = head1.next
tail = tail.next
tail.next = head2
head2 = head2.next
tail = tail.next
if head1:
tail.next = head1
if head2:
tail.next = head2
return dummy.next
# 输入单链表 LA 中的数据
inputs1 = list(map(int, input().split()))[:-1]
# 建立单链表 LA
dummy1 = ListNode()
tail1 = dummy1
for val in inputs1:
tail1.next = ListNode(val)
tail1 = tail1.next
head1 = dummy1.next
# 输入单链表 LB 中的数据
inputs2 = list(map(int, input().split()))[:-1]
# 建立单链表 LB
dummy2 = ListNode()
tail2 = dummy2
for val in inputs2:
tail2.next = ListNode(val)
tail2 = tail2.next
head2 = dummy2.next
# 合并单链表 LA 和 LB
new_head = merge_linked_lists(head1, head2)
# 输出合并后的单链表数据
while new_head:
print('--', new_head.val, end='')
new_head = new_head.next
print()
```
其中,`merge_linked_lists` 函数实现了两个单链表的合并操作,它接受两个链表头结点作为输入,返回合并后的链表头结点。建立原单链表的部分使用了哑结点(dummy node)技巧,最后将其丢弃即可。
阅读全文