分别输入两个有序的整数序列(分别包含M和N个数据),建立两个有序的单链表,将这两个有序单链表合并成为一个有序单链表,并依次输出合并后的单链表数据。
时间: 2023-10-30 19:08:02 浏览: 117
实现两个有序单链表的合并
5星 · 资源好评率100%
假设有两个有序单链表 A 和 B,我们需要将它们合并成一个有序单链表 C。具体的步骤如下:
1. 创建一个新的空链表 C。
2. 分别从链表 A 和 B 的头部开始遍历,比较两个节点的值的大小,将较小的那个节点加入链表 C 中,并将指针后移。
3. 如果链表 A 或 B 中有一个遍历到了结尾,则将另外一个链表的剩余节点全部加入链表 C 中。
4. 遍历结束后,链表 C 就是合并后的有序单链表。
下面是 Python 代码实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0)
cur = dummy
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 if l1 else l2
return dummy.next
```
其中,ListNode 表示单链表中的一个节点,val 表示节点的值,next 表示指向下一个节点的指针。mergeTwoLists 函数接受两个参数 l1 和 l2,分别表示两个有序单链表的头节点,返回合并后的有序单链表的头节点。dummy 表示合并后的有序单链表的虚拟头节点,cur 表示当前节点的指针。在遍历两个链表的过程中,不断比较两个节点的值的大小,将较小的那个节点加入链表 C 中,并将指针后移。最后,如果链表 A 或 B 中有一个遍历到了结尾,则将另外一个链表的剩余节点全部加入链表 C 中。
阅读全文