連結清單
合并兩個有序連結清單
1. 題目描述
難易度:簡單
将兩個升序連結清單合并為一個新的 升序 連結清單并傳回。新連結清單是通過拼接給定的兩個連結清單的所有節點組成的。
示例:
輸入:1->2->4, 1->3->4
輸出:1->1->2->3->4->4
來源:力扣(LeetCode)
連結:https://leetcode-cn.com/problems/merge-two-sorted-lists
2. 思路分析
- 周遊兩個連結清單,每次取到兩個結點的值進行比較
- 建立新的節點,值為取到的兩個結點中值較小的結點
- 将建立的結點加入到結果中
3. 代碼示範
/**
* @Description: TODO
* @Author YunShuaiWei
* @Date 2020/7/5 19:43
* @Version
**/
public class Solution {
private ListNode res = null;
private ListNode cur = res;
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
//利用兩個臨時變量node1和node2來周遊連結清單
ListNode node1 = l1;
ListNode node2 = l2;
while (node1 != null && node2 != null) {
//l1中val<l2中的val
if (node1.val < node2.val) {
//建立新的節點,并連結到res的next域
if (res == null) {
res = new ListNode(node1.val);
cur = res;
} else {
cur.next = new ListNode(node1.val);
cur = cur.next;
}
node1 = node1.next;
} else {
if (res == null) {
res = new ListNode(node2.val);
cur = res;
} else {
cur.next = new ListNode(node2.val);
cur = cur.next;
}
node2 = node2.next;
}
}
if (node1 == null) {
cur.next = node2;
} else {
cur.next = node1;
}
return res;
}
}
class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyZuBnL4MzNyUzN0AjM1AzNwAjMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)