Code & Func

打卡，第五天

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

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

1
ListNode *mergeList(ListNode *l1,ListNode *l2){
2
  if (!l1) return l2;
3
  else if (!l2) return l1;
4
  ListNode* ret = new ListNode(0);
5
  ListNode*p = ret;
6
  while(l1 && l2) {
7
    if (l1->val > l2->val) {
8
      ret->next = l2;
9
      ret = ret->next;
10
      l2 = l2->next;
11
    } else {
12
      ret->next = l1;
13
      ret = ret->next;
14
      l1 = l1->next;
15
    }
6 collapsed lines
16
  }
17
  ret->next = (l1)?l1:l2;
18
  ret = p->next;
19
  delete p;
20
  return ret;
21
}

这次做一个小改进（可能时间复杂度上没有改进）：

1
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
2
        ListNode* head = new ListNode(0);
3
        ListNode* ret = head;
4
        while(l1 || l2) {
5
            if ((l1 && l2 && l1->val > l2->val )|| !l1) {
6
                head->next = l2;
7
                head = head->next;
8
                l2 = l2->next;
9
            }else {
10
                head->next = l1;
11
                head = head->next;
12
                l1 = l1->next;
13
            }
14
        }
15
        head = ret->next;
3 collapsed lines
16
        delete ret;
17
        return head;
18
    }

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