Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

这题要求合并两个已经排好序的链表，很简单的题目，直接上代码：

  1. class Solution {
  2. public:
  3.     ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
  4.         ListNode dummy(0);
  5.         ListNode* p = &dummy;
  7.         while(l1 && l2) {
  8.             int val1 = l1->val;
  9.             int val2 = l2->val;
  10.             //哪个节点小，就挂载，同时移动到下一个节点
  11.             if(val1 < val2) {
  12.                 p->next = l1;
  13.                 p = l1;
  14.                 l1 = l1->next;
  15.             } else {
  16.                 p->next = l2;
  17.                 p = l2;
  18.                 l2 = l2->next;
  19.             }
  20.         }
  22.         //这里处理还未挂载的节点
  23.         if(l1) {
  24.             p->next = l1;
  25.         } else if(l2) {
  26.             p->next = l2;
  27.         }
  29.         return dummy.next;
  30.     }
  31. };

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

这题需要合并k个排好序的链表，我们采用divide and conquer的方法，首先两两合并，然后再将先前合并的继续两两合并。时间复杂度为O(NlgN)。

代码如下：

  1. class Solution {
  2. public:
  3.      ListNode *mergeKLists(vector<ListNode *> &lists) {
  4.         if(lists.empty()) {
  5.             return NULL;
  6.         }
  8.         int n = lists.size();
  9.         while(n > 1) {
  10.             int k = (n + 1) / 2;
  11.             for(int i = 0; i < n / 2; i++) {
  12.                 //合并i和i + k的链表，并放到i位置
  13.                 lists[i] = merge2List(lists[i], lists[i + k]);
  14.             }
  15.             //下个循环只需要处理前k个链表了
  16.             n = k;
  17.         }
  18.         return lists[0];
  19.     }
  21.     ListNode* merge2List(ListNode* n1, ListNode* n2) {
  22.         ListNode dummy(0);
  23.         ListNode* p = &dummy;
  24.         while(n1 && n2) {
  25.             if(n1->val < n2->val) {
  26.                 p->next = n1;
  27.                 n1 = n1->next;
  28.             } else {
  29.                 p->next = n2;
  30.                 n2 = n2->next;
  31.             }
  32.             p = p->next;
  33.         }
  35.         if(n1) {
  36.             p->next = n1;
  37.         } else if(n2) {
  38.             p->next = n2;
  39.         }
  41.         return dummy.next;
  42.     }
  43. };