題目鏈接：21. 合并兩個有序鏈表 - 力扣（LeetCode）
題目描述
將兩個升序鏈表合并為一個新的?升序?鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。?
示例 1：
輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]
示例 2：
輸入：l1 = [], l2 = []
輸出：[]
示例 3：
輸入：l1 = [], l2 = [0]
輸出：[0]
題目作答
-
雙指針遍歷：使用兩個指針分別遍歷兩個鏈表，比較當前節點值的大小，選擇較小值的節點加入新鏈表。
-
遞歸或迭代：
-
遞歸：通過遞歸調用合并剩余部分，代碼簡潔但可能導致棧溢出。
-
迭代：使用迭代模擬遞歸過程，通過虛擬頭節點簡化邊界處理。
-
-
邊界處理：若任一鏈表為空，直接返回另一鏈表；合并完成后，將剩余鏈表直接連接到結果末尾。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {// 邊界條件：若任一鏈表為空，返回另一鏈表if (!list1) return list2;if (!list2) return list1;// 遞歸合并if (list1->val <= list2->val) {list1->next = mergeTwoLists(list1->next, list2);return list1;} else {list2->next = mergeTwoLists(list1, list2->next);return list2;}}
};
