剑指 Offer 25. 合并两个排序的链表【递归、迭代】
题目描述
输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1:
1 | 输入:1->2->4, 1->3->4 |
限制:
1 | 0 <= 链表长度 <= 1000 |
解题思路
方法一:迭代
使用伪头结点,比较两个链表,将值小的链条通过尾插入法 插入到伪结点的链表中,直到其中一方结束,接着将不为空的一方直接加入到伪结点的链表的尾部。
代码实现
1 | public ListNode mergeTwoLists(ListNode l1, ListNode l2) { |
复杂度分析
时间复杂度:O(m+n)
空间复杂度:O(1)
方法二:递归
代码实现
1 | public ListNode mergeTwoLists2(ListNode l1, ListNode l2) { |
复杂度分析
时间复杂度:O(m+n)
空间复杂度:O(n+m) //递归调用栈
资源
剑指 Offer 25. 合并两个排序的链表【递归、迭代】
You need to set
install_url
to use ShareThis. Please set it in _config.yml
.