【leetcode刷題】6.合并有序連結清單——Java版

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)

🌈尋寶

⭐今天是堅持刷題更文的第6/100天

⭐各位的點贊、關注、收藏、評論、訂閱就是一條創作的最大動力

⭐更多算法題歡迎關注專欄《leetcode》

為了回饋各位粉絲，禮尚往來，給大家準備了一條多年積累下來的優質資源，包括 學習視訊、面試資料、珍藏電子書等

怎麼領取請大家自己找，尋寶遊戲現在開始。

找不到可以評論留言，一條就會注意到你。

如果還不行，請私信我。