23. Merge k Sorted Lists

Problem’s Link

—————————————————————————-

Mean:

将k个有序链表合并为一个有序链表.

analyse:

方法一：本着不重复发明轮子的原则，使用两两合并，就可以利用前面已经做过的Merge two Sorted Lists.

方法二：抖机灵.将所有结点的val都push_back在一个vector容器中，排序后又重新构造链表.

Time complexity: O(N)

view code

方法一：

  ListNode

  *

  mergeKLists(

  vector

  <

  ListNode

  *>

  &

  lists)

  {

  if(

  lists

  .

  empty

  ()){

  return

  nullptr;

  }

  while(

  lists

  .

  size()

  >

  1

  ){

  lists

  .

  push_back(

  mergeTwoLists(

  lists

  [

  0

  ],

  lists

  [

  1

  ]));

  lists

  .

  erase(

  lists

  .

  begin());

  lists

  .

  erase(

  lists

  .

  begin());

  }

  return

  lists

  .

  front();

  }

  ListNode

  *

  mergeTwoLists(

  ListNode

  *

  l1

  ,

  ListNode

  *

  l2)

  {

  if(

  l1

  ==

  nullptr

  ){

  return

  l2;

  }

  if(

  l2

  ==

  nullptr

  ){

  return

  l1;

  }

  if(

  l1

  ->

  val

  <=

  l2

  ->

  val

  ){

  l1

  ->

  next

  =

  mergeTwoLists(

  l1

  ->

  next

  ,

  l2);

  return

  l1;

  }

  else

  {

  l2

  ->

  next

  =

  mergeTwoLists(

  l1

  ,

  l2

  ->

  next);

  return

  l2;

  }

  }

方法二：

/**

 * —————————————————————–

 * Copyright (c) 2016 crazyacking.All rights reserved.

 * —————————————————————–

 *       Author: crazyacking

 *       Date  : 2016-02-18-09.02

 */

#include <queue>

#include <cstdio>

#include <set>

#include <string>

#include <stack>

#include <cmath>

#include <climits>

#include <map>

#include <cstdlib>

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

using
namespace
std;

typedef
long
long(
LL);

typedef
unsigned
long
long(
ULL);

const
double
eps(
1e-8); 
  // Definition for singly-linked list.
  
  struct
  ListNode
  
  {
   
  int
  val;
  
  ListNode
  *
  next;
  
  ListNode(
  int
  x)
  :
  val(
  x
  ),
  next(
  NULL)
  {}
  
  }; 
  class
  Solution
  
  {
   
  public
  :
  
  ListNode
  *
  mergeKLists(
  vector
  <
  ListNode
  *>&
  lists)
  
  {
   
  vector
  <
  int
  >
  nodeVal;
  
  for(
  auto
  ptr:
  lists)
  
  {
   
  while(
  ptr)
  
  {
   
  nodeVal
  .
  push_back(
  ptr
  ->
  val);
  
  ptr
  =
  ptr
  ->
  next;
  
  }
  
  }
  
  if(
  nodeVal
  .
  size()
  <=
  0)
  
  {
   
  return
  nullptr;
  
  } 
        
  sort(
  nodeVal
  .
  begin
  (),
  nodeVal
  .
  end());
  
  bool
  isFirst
  =
  1;
  
  ListNode
  *
  res
  =
  nullptr
  ,
  *
  head
  =
  nullptr;
  
  for(
  auto
  p:
  nodeVal)
  
  {
   
  if(
  isFirst)
  
  {
   
  isFirst
  =
  0;
  
  head
  =
  new
  ListNode(p);
  
  res
  =
  head;
  
  }
  
  else
  
  {
   
  head
  ->
  next
  =
  new
  ListNode(p);
  
  head
  =
  head
  ->
  next;
  
  }
  
  }
  
  return
  res;
  
  }
  
  }; 
  ListNode
  *
  getList(
  vector
  <
  int
  >&
  arr)
  
  {
   
  bool
  isFirst
  =
  1;
  
  ListNode
  *
  res
  =
  nullptr
  ,
  *
  head
  =
  nullptr;
  
  for(
  auto
  p:
  arr)
  
  {
   
  if(
  isFirst)
  
  {
   
  isFirst
  =
  0;
  
  head
  =
  new
  ListNode(p);
  
  res
  =
  head;
  
  }
  
  else
  
  {
   
  head
  ->
  next
  =
  new
  ListNode(p);
  
  head
  =
  head
  ->
  next;
  
  }
  
  }
  
  return
  res;
  
  } 
  int
  main()
  
  {
   
  Solution
  solution;
  
  int n;
  
  while(
  cin
  >>n)
  
  {
   
  vector
  <
  ListNode
  *>
  listVe;
  
  while(n
  —)
  
  {
   
  int
  num;
  
  cin
  >>
  num;
  
  vector
  <
  int
  >
  ve;
  
  for(
  int
  i
  =
  0;
  i
  <
  num;
  ++
  i)
  
  {
   
  int
  tmp;
  
  cin
  >>
  tmp;
  
  ve
  .
  push_back(
  tmp);
  
  }
  
  listVe
  .
  push_back(
  getList(
  ve));
  
  }
  
  ListNode
  *
  head
  =
  solution
  .
  mergeKLists(
  listVe);
  
  while(
  head)
  
  {
   
  cout
  <<
  head
  ->
  val
  <<
  ” “;
  
  head
  =
  head
  ->
  next;
  
  }
  
  cout
  <<
  “End.”
  <<
  endl;
  
  }
  
  return
  0;
  
  }
  
  /* 
  */