问题描述
解法
分析
Python 实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
|
class : def mergeTwoLists(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ if l1 is None: return l2 if l2 is None: return l1 if l1.val < l2.val: l1.next = self.mergeTwoLists(l1.next, l2) return l1 else: l2.next = self.mergeTwoLists(l1, l2.next) return l2
|
Java 实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
|
* Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class { 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; } } }
|
时间复杂度
O(m+n).
空间复杂度
O(m+n).
链接
21. Merge Two Sorted Lists
21. 合并两个有序链表
(English version) Algorithm Notes: Leetcode#21 Merge Two Sorted Lists
近期评论