先提前劇透一下，大家要好好做這一題，因為148題會用到這一題…
——leetcode此題熱評
前言
xdm,現在是早上
8：14，窗外下著小雨我是一條，我在做
leetcode第21題加油！
Question
難度：簡單
將兩個升序鏈表合并為一個新的升序鏈表并回傳，新鏈表是通過拼接給定的兩個鏈表的所有節點組成的，
示例 1：
輸入：l1 = [1,2,4], l2 = [1,3,4] 輸出：[1,1,2,3,4,4]示例 2：
輸入：l1 = [], l2 = [] 輸出：[]示例 3：
輸入：l1 = [], l2 = [0] 輸出：[0]提示：
兩個鏈表的節點數目范圍是 [0, 50] -100 <= Node.val <= 100 l1 和 l2 均按 非遞減順序 排列
Solution
不知道大家還記得
合并有序陣列嗎?異曲同工
忘記的小伙伴可以先看一下
傳送門1
- 當
l1和l2都不是空鏈表時，判斷l1和l2哪一個鏈表的頭節點的值更小，將較小值的節點添加到結果里， - 當一個節點被添加到結果里之后，將對應鏈表中的節點向后移一位，
- 將非空鏈表接在合并鏈表的后面
- 對于鏈表操作，一般都需要維護一個當前節點的指標，可以再回看一下兩數相加幫助理解
Code
所有
leetcode代碼已同步至github歡迎
star
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode l3 = new ListNode(-1);
ListNode cur=l3;
while (l1!=null&&l2!=null){
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur=cur.next;
}
cur.next = l1 == null ? l2 : l1;
return l3.next;
}
}
Result
復雜度分析
- 時間復雜度：O(m+n)
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/290250.html
標籤：java
上一篇：JAVA多載和重寫（深入理解）