已知L1和L2为两个带有头结点的单链表,L1的各个数据递增排列,L2的各个数据也递增排列。这两个链表已经建立,两个单链表中的数据各不相同,请编写程序通过归并的方法将这两个单链表合并为一个单链表,要求合并后的单链表数据递增排列。
时间: 2024-10-21 07:15:14 浏览: 31
为了合并两个已排序的单链表 L1 和 L2,你可以创建一个新的空链表 L3,然后遍历两个输入链表,依次比较当前节点的数据,将较小的那个添加到新链表 L3 中,并移动相应的指针。这个过程会持续直到其中一个链表为空,然后将另一个链表剩余部分接到 L3 的尾部。以下是伪代码的描述:
```python
def merge_sorted_lists(head1, head2):
# 创建新的头节点和指针
dummy_head = ListNode(0) # 创建一个虚拟头节点
current = dummy_head
while head1 is not None and head2 is not None:
if head1.val < head2.val:
current.next = head1
head1 = head1.next
else:
current.next = head2
head2 = head2.next
current = current.next # 移动当前节点
# 将剩余链表连接到 L3
if head1 is not None:
current.next = head1
else:
current.next = head2
return dummy_head.next # 返回合并后的链表头节点
```
其中 `ListNode` 是链表节点的定义,包含一个 `val` 数据域和一个 `next` 指向下一个节点的引用。
阅读全文