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

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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode 21. 合并两个有序链表(C#实现)——链表,递归,迭代，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2291字，纯文字阅读大概需要4分钟。

内容图文

一、问题

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     }

 

内容总结

以上是互联网集市为您收集整理的LeetCode 21. 合并两个有序链表(C#实现)——链表,递归,迭代全部内容，希望文章能够帮你解决LeetCode 21. 合并两个有序链表(C#实现)——链表,递归,迭代所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/647139.html

来源：【匿名】