双指针合并升序链表（双解）
题目
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
Python双解法
解法一（递归）
class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: if not list1: return list2 if not list2: return list1 if list1.val < list2.val: res = list1 res.next = self.mergeTwoLists(list1.next,list2) else : res = list2 res.next = self.mergeTwoLists(list1,list2.next) return res代码核心在于if-else语句中的递归逻辑
每次选值更小的那个节点当 “当前头”
把它的next指向剩下两个链表的合并结果
递归到底，最后串成一条有序链表
解法二（迭代）
class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode(-1) cur = dummy while list1 and list2: if list1.val < list2.val: cur.next = list1 list1 = list1.next else: cur.next = list2 list2 = list2.next cur = cur.next cur.next = list1 if list1 else list2 return dummy.next关键在于，while循环语句和最后的链表拼接
如果2的值大于1，则创建链表的节点直接指向1的链表，链表1自身向后移动，链表2的情况也同理。
cur.next = list1 if list1 list2。剩下的链表最多只有一个不为空，可以直接拼接。
Java解法
解法一（递归）
class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { if (list1 == null){ return list2; } if (list2 == null){ return list1; } if (list1.val < list2.val){ list1.next = mergeTwoLists(list1.next,list2); return list1; } else { list2.next = mergeTwoLists(list1,list2.next); return list2; } } }解法二（迭代）
class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode prehead = new ListNode(-1); ListNode cur = prehead; while (list1!=null && list2!=null){ if (list1.val <= list2.val){ cur.next = list1; list1 = list1.next; }else{ cur.next = list2; list2 = list2.next; } cur = cur.next; } cur.next = list1 == null ? list2 : list1; return prehead.next; } }C语言解法
解法一（递归）
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) { // 边界条件：一个为空，返回另一个 if (l1 == NULL) { return l2; } if (l2 == NULL) { return l1; } // 谁小谁当头，递归合并剩下的 if (l1->val < l2->val) { l1->next = mergeTwoLists(l1->next, l2); return l1; } else { l2->next = mergeTwoLists(l1, l2->next); return l2; } }解法二（迭代）
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) { // 创建虚拟头节点（dummy） struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode)); dummy->val = -1; dummy->next = NULL; // 工作指针，用来拼接链表 struct ListNode* cur = dummy; // 两个链表都不为空时，谁小拼接谁 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) ? l1 : l2; // 返回真正的头节点 return dummy->next; }总结
此题运用了递归和迭代两种方法，并且多种语言对比，有助于大家加深语言印象。