剑指 Offer 25. 合并两个排序的链表【递归、迭代】

题目描述

输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1:

1
2
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

限制:

1
0 <= 链表长度 <= 1000

解题思路

方法一:迭代

使用伪头结点,比较两个链表,将值小的链条通过尾插入法 插入到伪结点的链表中,直到其中一方结束,接着将不为空的一方直接加入到伪结点的链表的尾部。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummyHead=new ListNode(-1);
ListNode cur=dummyHead;
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?l2:l1;
return dummyHead.next;
}

复杂度分析

时间复杂度:O(m+n)

空间复杂度:O(1)

方法二:递归

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if(l2==null){
return l1;
}
ListNode res=null;
if (l1.val <= l2.val) {
res=l1;
res.next=mergeTwoLists2(l1.next,l2);
} else {
res=l2;
res.next=mergeTwoLists2(l1,l2.next);
}
return res;
}

复杂度分析

时间复杂度:O(m+n)

空间复杂度:O(n+m) //递归调用栈

资源

  1. https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/
  2. 《剑指offer》

剑指 Offer 25. 合并两个排序的链表【递归、迭代】

http://example.com/2021/04/19/25-合并两个排序的链表/

Author

John Doe

Posted on

2021-04-19

Updated on

2021-06-08

Licensed under

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments

You forgot to set the shortname for Disqus. Please set it in _config.yml.