【算法-Java实现】合并两个有序链表

【算法-Java实现】合并两个有序链表

一.问题描述：

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

二.问题解答：

方法：递归

如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。 本题解析：Leetcode21

觉得讲的比较通俗易懂的：画解算法

三.算法分析：

1.时间复杂度为O(n+m)。该问题需要对两个链表的所有节点进行判断，时间复杂度取决于两个链表的节点个数。

2.额外空间复杂度为O(n+m)。递归的本质就是调用计算机栈，栈的大小取决于递归调用的深度(深度即为两个链表的节点个数)。

3.递归：递归就是程序运行时自己调用自己，一个递归过程就是出入栈的过程。

使用递归时应该考虑1.如何设计递归函数 2.递归的终止条件

代码如下

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1==null){ return l2; }else if(l2==null){ return l1; }else if(l1.val<l2.val){ l1.next=mergeTwoLists(l1.next,l2); return l1; }else { l2.next=mergeTwoLists(l1,l2.next); return l2; } } }