数据结构已知L1和L2为两个带有头结点的单链表,L1的各个数据递增排列,L2的各个数据也递增排列。这两个链表已经建立,两个单链表中的数据各不相同,请编写程序通过归并的方法将这两个单链表合并为一个单链表,要求合并后的单链表数据递增排列。
时间: 2024-10-21 13:03:24 浏览: 36
为了将两个升序排列的单链表 L1 和 L2 合并成一个新的升序链表,你可以采用迭代或递归的方式来实现。这里是一个基本的迭代方法:
1. 首先创建一个新的头节点 `newHead`,用于存放合并后的链表。
2. 定义两个指针 `p1` 和 `p2` 分别指向 L1 和 L2 的头节点。
3. 当两个指针都存在并且其中有一个链表的当前节点值小于另一个时,选择较小的值节点作为新的链表节点,并移动对应指针到下一个节点。
4. 重复步骤3,直到其中一个链表遍历完。
5. 如果还有剩余节点未处理,则将另一个链表剩下的部分添加到最后。
以下是Python代码示例:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_sorted_lists(l1, l2):
newHead = ListNode(0) # 创建新链表的头节点
current = newHead # 当前节点指针
while l1 and l2: # 只要l1和l2都有节点
if l1.val < l2.val: # 将较小值的节点添加到新链表
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next # 移动当前节点指针
# 将剩余未处理的节点连接到新链表的末尾
if l1:
current.next = l1
elif l2:
current.next = l2
return newHead.next # 返回合并后的新链表头节点
# 使用示例
l1 = ListNode(1, ListNode(3, ListNode(5)))
l2 = ListNode(2, ListNode(4))
merged_list = merge_sorted_lists(l1, l2)
```
阅读全文