LeetCode 21. 合并两个有序链表(C#实现)——链表,递归,迭代

一、问题

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             else26             {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                 else50                 {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     }

 

来源：https://www.icode9.com/content-1-608901.html