给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]nums2 = [2]则中位数是 2.0
示例 2:
nums1 = [1, 2]nums2 = [3, 4]则中位数是 (2 + 3)/2 = 2.5
接下来给出上一个算法【两数相加】的答案：
在解此题千万不要将链表转为int或者long进行计算，然后再转为链表，因为给个这个链表的数可能非常大，超出这些数据类型的最大长度。
思路
我们先创建一个头节点为0的链表用于存储我们的结果
然后我们同时遍历两个列表，分别取出两个链表的第一个元素，进行加和，然后对10取余，将取余之后的数放入第1步创建的链表的next，然后再对10取商，作为下一个节点要进位的值
然后遍历两个链表的第二个元素，也是做上述同样的操作，但是这个时候要注意的是，这个时候有可能某一个链表没有第二个元素，那我们判断入股某一个链表没有元素了，我们直接赋值0即可。
继续重复以上操作，直到两个链表全部遍历完
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode dummyHead = new ListNode(0);ListNode p = l1, q = l2, curr = dummyHead;int carry = 0;while (p != null || q != null) {int x = (p != null) ? p.val : 0;int y = (q != null) ? q.val : 0;int sum = carry + x + y;carry = sum / 10;curr.next = new ListNode(sum % 10);curr = curr.next;if (p != null) p = p.next;if (q != null) q = q.next;}if (carry > 0) {curr.next = new ListNode(carry);}return dummyHead.next;}
复杂度分析
时间复杂度：O(max(m, n))，假设 m 和 n 分别表示 l1 和 l2 的长度，上面的算法最多重复 max(m, n)次。
空间复杂度：O(max(m, n))， 新列表的长度最多为 max(m,n) + 1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
本文分享自微信公众号 - 自增程序员（javaipp）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
