将两个递增单链表合并

将两个递增有序的单链表合并成一个新的递增有序链表，可以采用迭代或递归的方式解决。这里提供一种常见的迭代方法：

创建一个新的头结点 new_head 和指针 current，初始时它们都指向新链表的头部。

分别遍历两个输入链表，比较当前节点的值。将较小的那个节点添加到新的链表中，并更新当前指针。

当其中一个链表遍历完后，将另一个链表剩余的部分直接连接到新链表的末尾。

最终，current 指向的就是合并后的链表的最后一个节点。

以下是伪代码示例：
def merge_sorted_lists(list1, list2):
new_head = Node(0) # 新链表的头节点，初始化为0
current = new_head

while list1 and list2:
if list1.val < list2.val:
current.next = list1
list1 = list1.next
else:
current.next = list2
list2 = list2.next
current = current.next

# 如果其中一个链表已经遍历完，把剩下的加到新链表末尾
if list1:
current.next = list1
elif list2:
current.next = list2

return new_head.next
登录后复制