将两个非递减的有序链表,合并成一个非递减的有序链表。
时间: 2024-09-25 11:17:39 浏览: 34
基于链表的两个非递减有序序列的合并.docx
将两个非递减的有序链表合并成一个非递减的有序链表是一种常见的链表操作,通常采用迭代或递归的方式实现。这里提供一种简单的迭代解决方案:
1. 首先创建一个新的头节点,并让它指向一个空链表。
2. 创建两个指针,分别指向第一个链表的头和第二个链表的头。
3. 比较当前两个指针所指向的节点的值,选择较小的一个节点(如果它们相等则任选一个),将其添加到新链表中,并移动该节点的指针。
4. 如果当前链表还有剩余元素,则继续上述步骤,将另一个链表的下一个元素与当前链表的下一个元素比较并添加。
5. 当其中一个链表遍历完时,将另一个链表剩余的部分直接添加到新链表的末尾。
这个过程保证了新链表始终是有序的。下面是伪代码形式:
```
new_head = ListNode(0) # 初始化新链表的头结点
current = new_head
while list1_head and list2_head: # 只有当两个链表都不为空
if list1_head.val <= list2_head.val:
current.next = list1_head
list1_head = list1_head.next
else:
current.next = list2_head
list2_head = list2_head.next
current = current.next
# 添加最后一个链表的所有元素
if list1_head:
current.next = list1_head
else:
current.next = list2_head
```
阅读全文