您将得到两个排序整数的双链表(按升序排列)。设L和R是这两个双链表的头指针。编写一个算法,将它们合并成一个排序的整数链表。请写出具体的代码
时间: 2024-09-30 19:04:57 浏览: 37
要将两个已排序的整数双链表合并成一个新的有序链表,可以创建一个新的链表,并通过迭代的方式逐一比较和链接节点。这里是一个基于Python的示例代码:
```python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
self.prev = None
def merge_sorted_lists(l1, l2):
dummy = ListNode(0) # 创建虚拟头节点
current = dummy # 当前节点指向虚拟头
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 dummy.next # 返回新链表的头节点
# 示例:
l1 = ListNode(1)
l1.next = ListNode(2)
l1.next.next = ListNode(4)
l2 = ListNode(1)
l2.next = ListNode(3)
l2.next.next = ListNode(4)
merged_list = merge_sorted_lists(l1, l2)
```
在这个例子中,`merge_sorted_lists`函数接收两个链表的头节点作为输入,通过遍历并比较节点值,逐步构建新的有序链表。最后返回新链表的第一个实际节点。
阅读全文