输入两个逆序链表,合并成一个升序链表并输出
时间: 2024-10-10 10:02:42 浏览: 34
当你有两个逆序的单链表需要合并成一个升序的链表时,可以采用双指针法和迭代的方式来解决这个问题。以下是步骤:
1. 创建一个新的头节点`newHead`,初始值设为None,用于存储合并后的链表。
2. 定义两个指针`p1`和`p2`分别指向第一个逆序链表的头节点和第二个逆序链表的头节点。
3. 比较两个指针所指向的元素,将较小的那个节点添加到新链表中,并移动该节点指向前一个较小节点,同时更新`p1`和`p2`指向下一个节点。如果其中一个链表遍历完,则直接将另一个链表剩余的部分添加到新链表的后面。
4. 当两个指针都遍历完成后,`newHead`指向的就是合并后的升序链表的头节点。
5. 最后,返回`newHead`作为结果。
这是一个典型的链表操作问题,可以用Python的伪代码表示如下:
```python
def merge_sorted_lists(l1, l2):
new_head = ListNode(None) # 新链表的头
current = new_head
while l1 and l2: # 只要l1和l2任一链表还有元素
if l1.val < l2.val: # 如果l1的元素更小
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 new_head.next # 返回合并后的升序链表的第一个节点
```
阅读全文