一、问题
https://leetcode-cn.com/problems/merge-two-sorted-lists/
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
二、GitHub实现：https://github.com/JonathanZxxxx/LeetCode/blob/master/MergeTwoListsClass.cs
Blog：https://www.cnblogs.com/zxxxx/
三、思路
1、递归：判断两个链表的头元素大小，递归的决定下一个添加进结果的值
2、迭代：设定哨兵节点head，维护一个prev指针，每次迭代都是调整prev的next指针，判断两个链表头元素大小，将小的值接入prev节点后面，同时将接入的链表和prev后移
四、代码实现
1 public class MergeTwoListsClass 2 { 3 public class ListNode 4 { 5 public int val; 6 public ListNode next; 7 public ListNode(int x) { val = x; } 8 } 9 10 /// <summary> 11 /// 递归 12 /// </summary> 13 /// <param name="l1"></param> 14 /// <param name="l2"></param> 15 /// <returns></returns> 16 public ListNode MergeTwoLists(ListNode l1, ListNode l2) 17 { 18 if (l1 == null) return l2; 19 else if (l2 == null) return l1; 20 else if (l1.val < l2.val) 21 { 22 l1.next = MergeTwoLists(l1.next, l2); 23 return l1; 24 } 25 else 26 { 27 l2.next = MergeTwoLists(l2.next, l1); 28 return l2; 29 } 30 } 31 32 /// <summary> 33 /// 迭代 34 /// </summary> 35 /// <param name="l1"></param> 36 /// <param name="l2"></param> 37 /// <returns></returns> 38 public ListNode MergeTwoLists2(ListNode l1, ListNode l2) 39 { 40 var head = new ListNode(-1); 41 var prev = head; 42 while (l1 != null && l2 != null) 43 { 44 if (l1.val < l2.val) 45 { 46 prev.next = l1; 47 l1 = l1.next; 48 } 49 else 50 { 51 prev.next = l2; 52 l2 = l2.next; 53 } 54 prev = prev.next; 55 } 56 prev.next = l1 == null ? l2 : l1; 57 return head.next; 58 } 59 }