说实话,这个题我第一次没解出来,是看了别人的思路才搞定的,中间在边界问题上还错了n次。惭愧。
先说一下解题思路。
一开始我能想到的思路是:merge sort然后输出array[median]即可。但是很明显这样的时间复杂度高于o(log(m+n)),大概是o(m+n)的复杂度。
时间复杂度的限制是解这个题比较让人郁闷的地方。
ok,再看题目条件,两个已经排好序的数组,时间复杂度是log,这样很容易让人想到什么?二分查找?
但是怎么用二分来解这个题?这儿有一点点数学知识。
具体的推导请看链接:http://blog.chinaunix.net/uid-28490468-id-3576490.html
之前看到也是一篇博客,可是已经找不到了。囧
ListNode *l;</p> <p>class Solution { public: ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) { // Note: The Solution object is instantiated only once and is reused by each test case. l1 = Reverse(l1); l2 = Reverse(l2); ListNode *ans = NULL; ListNode *ansbackup = NULL; int sum = 0; int now = 0; int next = 0; while(true) { if(l1 == NULL || l2 == NULL) break; sum = l1->val + l2->val+next; now = sum % 10; next = sum / 10; ListNode *tmp = new ListNode(now); if(ans == NULL) { ans = tmp; ansbackup = ans; } else { ans->next = tmp; ans = ans->next; }<br /> l1 = l1->next; l2 = l2->next; } if(l1 != NULL) { while(true) { if(l1 == NULL)break; sum = l1->val + next; now = sum % 10; next = sum / 10; ListNode * tmp = new ListNode(now); ans->next = tmp; ans = ans->next; l1 = l1->next; } } if(l2 != NULL) { while(true) { if(l2 == NULL)break; sum = l2->val + next; now = sum % 10; next = sum / 10; ListNode *tmp = new ListNode(now); ans->next = tmp; ans = ans->next; l2 = l2->next; } } if(next != 0) { ListNode *tmp = new ListNode(next); ans->next = tmp; ans = ans->next; } return ansbackup; } ListNode *Reverse(ListNode *l) {<br /> ListNode * before; ListNode * now; ListNode * next; if(l->next == NULL) return l; before = l; now = l->next; while(now == NULL) { next = now->next; now->next = before; before = now; now = next; } return before; } };