LeetCode刷题笔记：合并两个有序链表（0021）

题目链接

https://leetcode.cn/problems/merge-two-sorted-lists/

题目描述

给定两个按非递减顺序排列的单链表 list1 和 list2，将它们合并为一个新的有序链表并返回。

解题思路

• 迭代合并：
  • 使用哑节点 dummy 和指针 cur。
  • 每次从 list1、list2 取较小节点接到 cur 后面并前进对应链表。
  • 一方耗尽后，直接把另一方剩余部分接到末尾。
• 边界情况：若某一链表为空，答案即为另一链表。

题解代码

classSolution{publicListNodemergeTwoLists(ListNodelist1,ListNodelist2){ListNodedummy=newListNode();ListNodecur=dummy;while(list1!=null&&list2!=null){if(list1.val<list2.val){cur.next=list1;list1=list1.next;}else{cur.next=list2;list2=list2.next;}cur=cur.next;}cur.next=(list1!=null)?list1:list2;returndummy.next;}}

复杂度分析

• 时间复杂度：O(n + m)，n、m 分别为两链表长度。
• 空间复杂度：O(1)，除若干指针外不使用额外空间。