LeetCode 圖解 | 21.合并兩個有序連結清單

下面開始今天的學習～

今天分享的題目來源于 LeetCode 上第 21 号問題：合并兩個有序連結清單。

題目描述

将兩個有序連結清單合并為一個新的有序連結清單并傳回。新連結清單是通過拼接給定的兩個連結清單的所有節點組成的。 

示例：

輸入：1->3->4, 2->5->6
輸出：1->2->3->4->5->6      

題目解析

首先，設定一個虛拟節點 dummy 用來存儲結果，循環對比 ​

​L1​

​​ 和 ​

​L2​

​ 節點上的數字，通過調整 p節點的 next 指針來調整 dummy 的結果。

• 如果L1 目前位置的值小于等于 L2 ，我們就把  L1 的值接在  dummy 節點的後面同時将  L1 指針往後移一個
• 如果L2 目前位置的值小于 L2 ，我們就把  L2 的值接在  p 節點的後面同時将  L2 指針往後移一個
• 不管我們将哪一個元素接在了p 節點後面，都需要向後移一個元素
• 重複以上過程，直到L1 或者  L2 指向了 null 
• 在循環終止的時候，L1 和  L2 至多有一個是非空的。由于輸入的兩個連結清單都是有序的，是以不管哪個連結清單是非空的，它包含的所有元素都比前面已經合并連結清單中的所有元素都要大。這意味着我們隻需要簡單地将非空連結清單接在合并連結清單的後面，并傳回合并連結清單。

動畫了解

代碼實作

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
 //@程式員吳師兄
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), p = dummy;

    while (l1 != null && l2 != null) {
      if (l1.val < l2.val) {
        p.next = l1;
        l1 = l1.next;
      } else {
        p.next = l2;
        l2 = l2.next;
      }
      p = p.next;
    }

    if (l1 != null) p.next = l1;
    if (l2 != null) p.next = l2;
    return dummy.next;
    }
}      

複雜度分析

時間複雜度：O(m+n)，m 與 n 友善是連結清單的長度。每次循環疊代中，​

​L1​

​​ 和 ​

​L2​

​隻有一個元素會被放進合并連結清單中， while 循環的次數等于兩個連結清單的總長度。

空間複雜度：O(1)，疊代的過程隻會産生幾個指針，是以它所需要的空間是常數級别的。

相關題目推薦

• LeetCode 23：合并 K 個排序連結清單
• LeetCode 88：合并兩個有序數組
• LeetCode 148：排序連結清單
• LeetCode 244：最短單詞距離 II