已知L1和L2为两个带有头结点的单链表,L1的各个数据递增排列,L2的各个数据也递增排列。这两个链表已经建立,两个单链表中的数据各不相同,请编写程序通过归并的方法将这两个单链表合并为一个单链表,要求合并后的单链表数据递增排列。用数据结构的知识写这个代码
时间: 2024-10-17 11:05:59 浏览: 75
为了合并两个已排序的单链表 L1 和 L2,并保持结果链表递增排列,我们可以创建一个新的链表头节点 `mergedHead`,然后遍历两个输入链表,比较当前节点的数据,将较小的那个添加到新链表中,同时更新指向下一个待处理节点的指针。
这里是一个 Python 的示例代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_sorted_lists(l1, l2):
# 创建新链表的头节点和临时指针
mergedHead = ListNode(0)
current = mergedHead
# 当有一个链表结束时,另一个链表还有元素,则直接将其剩余部分添加到新链表
while l1 is not None and l2 is not None:
if l1.val < l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
# 将未遍历完的链表添加到新链表尾部
if l1 is not None:
current.next = l1
elif l2 is not None:
current.next = l2
return mergedHead.next # 返回合并后的链表头节点
# 示例链表构造
l1 = ListNode(1, ListNode(4))
l1.next.next = ListNode(5)
l2 = ListNode(2, ListNode(3))
# 合并并打印结果
result = merge_sorted_lists(l1, l2)
while result:
print(result.val, end=" -> ")
result = result.next
```
当你运行这段代码,它会输出:1 -> 2 -> 3 -> 4 -> 5 -> ,表示合并后的单链表数据递增排列。
阅读全文