您将得到两个排序整数的双链表(按升序排列)。设L和R是这两个双链表的头指针。编写一个算法,将它们合并成一个排序的整数链表。请将关键代码简易表述出来
时间: 2024-09-21 14:12:55 浏览: 71
合并两个有序的双链表 L 和 R 可以通过创建一个新的链表,并依次比较 L 和 R 的节点值来进行。以下是一个简化版的关键代码示例:
```python
class ListNode:
def __init__(self, val=0, next=None, prev=None):
self.val = val
self.next = next
self.prev = prev
def merge_sorted_lists(L, R):
# 初始化新链表头和临时指针
dummy = ListNode(0)
new_head = dummy
curr = dummy
# 当L和R都有节点时
while L and R:
# 如果L的节点小于R,将L的节点添加到新链表
if L.val <= R.val:
curr.next = L
L.prev = curr
curr = L
L = L.next
else: # 否则,将R的节点添加
curr.next = R
R.prev = curr
curr = R
R = R.next
# 添加剩下的链表尾部,如果有的话
curr.next = L or R
return dummy.next
```
这个代码首先创建了一个虚拟头节点 `dummy`,然后在循环中比较 L 和 R 的节点值,每次都将较小的节点添加到新链表中,并更新相应的指针。最后返回新链表的实际头节点 `dummy.next`。
阅读全文