7-3 两个有序链表序列的合并
时间: 2024-06-10 16:08:35 浏览: 179
合并两个有序链表的方法可以使用双指针法。首先,创建一个新的链表作为合并后的结果。然后,比较两个链表当前指针所指的节点的值,将较小的节点添加到新链表中,并将指针向后移动。当其中一个链表的指针为空时,将另一个链表剩余的部分直接添加到新链表的末尾。最后,返回新链表作为合并后的结果。
以下是Python实现的示例代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
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
if l1:
cur.next = l1
if l2:
cur.next = l2
return dummy.next
# 示例输入
# 第一行:1 3 5 -1
# 第二行:2 4 6 -1
l1 = ListNode(1)
l1.next = ListNode(3)
l1.next.next = ListNode(5)
l2 = ListNode(2)
l2.next = ListNode(4)
l2.next.next = ListNode(6)
merged = mergeTwoLists(l1, l2)
# 输出合并后的链表
while merged:
print(merged.val, end=' ')
merged = merged.next
```
阅读全文