回国一趟回来做题很难进入状态了，顺便问下

http://www.mitbbs.com//article_t/JobHunting/32817887.html

发信人: abcee (abcee), 信区: JobHunting
标  题: 回国一趟回来做题很难进入状态了，顺便问下那个Merge k Sorted Lists
发信站: BBS 未名空间站 (Thu Oct 30 14:10:46 2014, 美东)

回国一趟回来做题很难进入状态了，有类似经历的同学么？从6月份断断续续做还不到
100道，回来一看又增加了3道题，变154道了。再看版上讨论，觉得还得花多少时间啊
。也许根本就不适合搞这行，但又不知道做其他什么工作。

看到国内挣钱门路好多啊，大家都很潇洒的说。不知道怎么调整心态，急需换个工作或
者换种活法。

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

有人面试碰到这题么？我洋洋洒洒写了很多代码，OJ说Time Limit Exceeded

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        int n = lists.size();
        if (n==0) return NULL;
        ListNode *ret = lists[0];
        for (int i=1; i<n; i++)
        {
            ret = merge2Lists(ret, lists[i]);
        }
        return ret;
    }

private:
   ListNode *merge2Lists(ListNode *a, ListNode *b)
   {
       if (a==NULL&&b==NULL) return NULL;
      
       ListNode *r=NULL, *prev=NULL;
       if (a==NULL&&b!=NULL) return b;
       if (a!=NULL&&b==NULL) return a;
       ListNode dummy(-1);
       dummy.next = a->val>b->val?b:a;
       prev = dummy.next;
       if (dummy.next==a)
          a= a->next;
          else
          b=b->next;
      
       while(a!=NULL&&b!=NULL)
       {
           if (a->val<b->val)
           {
               prev->next = a;
               prev = a;
               a=a->next;
           }
           else
              {
                  prev->next=b;
                  prev = b;
                  b=b->next;
              }
       }
       prev->next = a!=NULL?a:b;
       return dummy.next;
   }

--