有两个单链表LA和LB,其元素均为递增有序序列,将它们合并成一个单链表LC,要求LC也是递增有序序列,且不增加新结点。 如LA=(2,4,4,6),LB=(1,3,3,5),则LC=(1,2,3,3,4,5,6)的代码
时间: 2024-10-20 09:05:41 浏览: 38
这是一个经典的链表合并问题,可以使用迭代的方式来解决。以下是使用Python的解决方案:
```python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def merge_sorted_lists(la, lb):
dummy = ListNode(0) # 创建虚拟头节点
current = dummy # 当前指针指向dummy
while la and lb: # 只要两个链表都不为空
if la.val <= lb.val: # 如果LA的值小或相等
current.next = la # 将LA的下一个节点连接到current
la = la.next # 移动LA指针
else: # 否则LA的值大
current.next = lb # 将LB的下一个节点连接到current
lb = lb.next # 移动LB指针
current = current.next # 指针向前移动
# 链表未遍历完的情况
if la is not None: # 如果LA还有剩余节点
current.next = la # 连接LA剩余的部分
elif lb is not None: # 如果LB还有剩余节点
current.next = lb # 连接LB剩余的部分
return dummy.next # 返回合并后的链表头部
# 示例链表创建
la = ListNode(2)
la.next = ListNode(4)
la.next.next = ListNode(4)
la.next.next.next = ListNode(6)
lb = ListNode(1)
lb.next = ListNode(3)
lb.next.next = ListNode(3)
lb.next.next.next = ListNode(5)
# 结果链表会是 [1, 2, 3, 3, 4, 5, 6]
merged_list = merge_sorted_lists(la, lb)
```
这个代码首先创建了一个虚拟头节点,然后在循环中比较两个链表当前节点的值,选择较小的那个添加到结果链表中,并相应地更新指针。最后返回合并后的实际头节点。
阅读全文