Merge Two Sorted List

Sep 28, 2017

打卡,第五天

今天偷个懒,找下自信先,做个Easy的题目——Merge Two Sorted List (我也没想到是这么简单的题目)

之前在 LintCode做个一个链表排序,也写过一篇blog 解这道题时用的是MergeSort去做.所以已经写过一次Merge Two Sorted List了,之前的写法是这样的:

ListNode *mergeList(ListNode *l1,ListNode *l2){
  if (!l1) return l2;
  else if (!l2) return l1;
  ListNode* ret = new ListNode(0);
  ListNode*p = ret;
  while(l1 && l2) {
    if (l1->val > l2->val) {
      ret->next = l2;
      ret = ret->next;
      l2 = l2->next;
    } else {
      ret->next = l1;
      ret = ret->next;
      l1 = l1->next;
    }
  }
  ret->next = (l1)?l1:l2;
  ret = p->next;
  delete p;
  return ret;
}

这次做一个小改进(可能时间复杂度上没有改进):

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode(0);
        ListNode* ret = head;
        while(l1 || l2) {
            if ((l1 && l2 && l1->val > l2->val )|| !l1) {
                head->next = l2;
                head = head->next;
                l2 = l2->next;
            }else {
                head->next = l1;
                head = head->next;
                l1 = l1->next;
            }
        }
        head = ret->next;
        delete ret;
        return head;
    }

恩,细细想想,这个思路效率可能跟慢,不过用在对数组的Merge的情况还是可以的(起码比较简洁)。

LeetCodeLeetCode链表

Add Two Numbers

Container With Most Water

comments powered by Disqus