文章目錄
- 題目來源
- 題目描述
- 解題思路
- 圖解
- 實作代碼
題目來源
https://leetcode-cn.com/problems/merge-two-sorted-lists/description/
題目描述
将兩個有序連結清單合并為一個新的有序連結清單并傳回。新連結清單是通過拼接給定的兩個連結清單的所有節點組成的。
示例:
輸入:1->2->4, 1->3->4
輸出:1->1->2->3->4->4
解題思路
- 首先得有一個新的虛拟節點
用來将這兩個連結清單串起來newHead
- 如圖這樣兩個有序單連結清單,
,遵守穩定性,将l1.val >= l2.val
串到l1
所在的新連結清單後面,然後newHead
後移一位l1
- 如果
的值大于l2
的值,就将l1
串到l2
所在的新連結清單,然後newHead
後移一位l2
- 如果
為空,就直接把l1
串到l2
所在的新連結清單後面newHead
- 如果
為空,就直接把l2
串到l1
所在的新連結清單後面newHead
- 最後傳回
節點,即新的頭節點newHead.next
圖解
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAzNfRHLGZkRGZkRfJ3bs92YsYTMfVmepNHL5lkeNNzY65keRpHW4Z0MMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnL1kTO0QzM1IjM1ATNwkTMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
實作代碼
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
/**
* newHead
* @param l1 List1's head
* @param l2 List2's head
* @return newList's newHead
*/
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//define a virtual head mark head
ListNode newHead = new ListNode(-1);
ListNode cur = newHead;
while (l1 != null && l2 !=null) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
cur = cur.next;
} else {
cur.next = l2;
l2 =l2.next;
cur =cur.next;
}
}
if (l1 == null) {
cur.next = l2;
}
if (l2 == null) {
cur.next = l1;
}
return newHead.next;
}