21. 合并两个有序链表
时间: 2024-06-09 13:10:13 浏览: 102
合并两个有序链表是指将两个已经按升序排列的链表合并成一个新的升序链表。可以使用迭代的方法来实现,首先定义一个哨兵节点 preHead 作为新链表的头部,然后定义一个指针 prev 指向 preHead。接下来,通过循环迭代比较 list1 和 list2 的节点值,将较小的节点接在 prev 的后面,然后将对应的指针向后移动一位。最后,将合并后剩余的链表直接接在 prev 的后面。最后返回 preHead.next 即可得到合并后的链表。
代码示例:
```python
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode preHead = new ListNode(-1);
ListNode prev = preHead;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
prev.next = list1;
list1 = list1.next;
} else {
prev.next = list2;
list2 = list2.next;
}
prev = prev.next;
}
prev.next = list1 == null ? list2 : list1;
return preHead.next;
}
}
```
时间复杂度分析:由于每次循环迭代中,只有一个元素被放入合并链表中,所以 while 循环的次数不会超过两个链表的长度之和,时间复杂度为 O(n + m)。空间复杂度为 O(1),只需要常数级别的额外空间。
阅读全文
相关推荐














