链表拼接:输入若干个正整数(输入-1微结束标志),建立两个已按升序排列的单向链表,头指针分别为list1、list2,把两个链表拼成一个链表,并输出新链表信息。要求自定义函数,实现将两个链表拼成一个链表,并返回拼组后的新链表。试编写相应程序。
时间: 2023-06-26 21:06:36 浏览: 114
链表_链表_用链表将两个数组升序合并到另一个数组_
以下是一个简单的实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def construct_linked_list():
head = None
while True:
val = int(input())
if val == -1:
break
node = ListNode(val)
if head is None:
head = node
else:
curr = head
while curr.next is not None:
curr = curr.next
curr.next = node
return head
def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0)
tail = dummy
while l1 is not None and l2 is not None:
if l1.val < l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
if l1 is not None:
tail.next = l1
else:
tail.next = l2
return dummy.next
if __name__ == '__main__':
print("请输入第一个链表的元素(已按升序排列),以-1结束:")
list1 = construct_linked_list()
print("请输入第二个链表的元素(已按升序排列),以-1结束:")
list2 = construct_linked_list()
merged_list = merge_two_lists(list1, list2)
print("合并后的链表为:")
while merged_list is not None:
print(merged_list.val, end=" ")
merged_list = merged_list.next
```
这里定义了一个 `ListNode` 类表示链表中的每个节点。`construct_linked_list` 函数用于构造链表,它会读入若干个正整数并将它们添加到链表中,直到读入 `-1` 为止。`merge_two_lists` 函数用于将两个已按升序排列的链表 `l1` 和 `l2` 拼接成一个新链表,它的返回值是拼接后的新链表的头节点。在 `main` 函数中,我们先读入两个链表,然后调用 `merge_two_lists` 函数将它们拼接起来,最后输出拼接后的链表。
阅读全文