LeetCode题库-21.合并两个有序链表解题方法
一般方法
遍历两个链表，一一对比取得的元素，把小的元素放入新的链表中 如l1=[1,2,4],l2=[1,3,4]
- 创建一个新的链表ListNode newListNode=null;
- 使用两个指针分别指向两个链表的第一个元素l1_1=1，l2_1=1;
- 比较两个元素，如果第一个大于等于第二个，则取第二个链表的元素，否则取第一个链表的元素,这里取到L2_1,放入newListNode；
- 第二个链表移动到下一个元素l2_2，第一个链表还是第一个元素，重复第三步，直到一个链表取完元素，
- 这是如果另一个链表还有元素，直接把剩下的元素放到新链表尾部，因为原来的链表本来就是有序的
代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public ListNode MergeTwoLists(ListNode l1, ListNode l2)
{
if (l1 == null)
{
return l2;
}
if (l2 == null)
{
return l1;
}
ListNode newListNode = null;
ListNode curListNode = null;
var curListNode1 = l1;
var curListNode2 = l2;
while (curListNode1 != null && curListNode2 != null)
{
ListNode curListNodeNext = null;
if (curListNode1.val > curListNode2.val)
{
curListNodeNext = new ListNode(curListNode2.val, null);
curListNode2 = curListNode2.next;
}
else
{
curListNodeNext = new ListNode(curListNode1.val, null);
curListNode1 = curListNode1.next;
}
if (curListNode == null)
{
curListNode = curListNodeNext;
newListNode = curListNode;
}
else
{
curListNode.next = curListNodeNext;
}
curListNode = curListNodeNext;
}
if (curListNode1 != null)
{
curListNode.next = curListNode1;
}
else if (curListNode2 != null)
{
curListNode.next = curListNode2;
}
return newListNode;
}
递归思想
参考答案使用的递归思想，这个做法和汉诺塔的解法差不多，就是先取出小的一个元素，剩下的交给其他方法去排序,只要理解了思想这种方式代码简单得多，比如你们领导分提成的时候说：我拿一半，剩下的你们分。然后第二个领导也说：我拿一半，剩下的你们分。最后到你这里还有一半，要是叫你写算法来计算提成，用递归要简单很多。
代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public ListNode MergeTwoLists(ListNode l1, 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;
}
}
参考资料
本文会经常更新，请阅读原文： https://dashenxian.github.io/post/21.%E5%90%88%E5%B9%B6%E4%B8%A4%E4%B8%AA%E6%9C%89%E5%BA%8F%E9%93%BE%E8%A1%A8 ，以避免陈旧错误知识的误导，同时有更好的阅读体验。
本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。欢迎转载、使用、重新发布，但务必保留文章署名 小神仙 （包含链接： https://dashenxian.github.io ），不得用于商业目的，基于本文修改后的作品务必以相同的许可发布。如有任何疑问，请 与我联系 (125880321@qq.com) 。