专业科技公司网站欣赏,nginx即代理又做网站,免费咨询协议,wordpress破解企业模板一、题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1#xff1a; 输入#xff1a;l1 [1,2,4], l2 [1,3,4]
输出#xff1a;[1,1,2,3,4,4]示例 2#xff1a;
输入#xff1a;l1 [], l2 []
输出#…一、题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1 输入l1 [1,2,4], l2 [1,3,4]
输出[1,1,2,3,4,4]示例 2
输入l1 [], l2 []
输出[]示例 3
输入l1 [], l2 [0]
输出[0]二、思路解析
在数据结构部分大家都见过这道题吧。我们这学期的期末考试大题也考了这一道不过本篇博客我们来讲讲递归解法。
合并有序链表无非就是要遍历这两个链表判断哪一个链表的节点值更小然后利用链表的性质重新串起即可。
所以递归的出口就是当某一个链表已经遍历到最后一个元素了因为这种情况就说明这个链表的节点值已经全部小于另一个链表了。
而递归函数体部分则直接比较两个链表的节点值即可然后把较小值的下一个节点继续与另一个链表递归。
具体实现请看下面代码
三、完整代码
/*** 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 list1, ListNode list2) {if(list1 null){return list2;}if(list2 null){return list1;}if(list1.val list2.val){list1.next mergeTwoLists(list1.next , list2);return list1;}else{list2.next mergeTwoLists(list1 , list2.next);return list2;}}
} 以上就是本篇博客的全部内容啦如有不足之处还请各位指出期待能和各位一起进步
