合并k个排序链表

题目描述

合并k个排序链表，并且返回合并后的排序链表。尝试分析和描述其复杂度。

思路

• 归并。

  • 对左半部分的链表排序，排序后返回一个链表A
  • 对右半部分的链表排序，排序后返回一个链表B
  • 对链表A和链表B排序
    这样做，每次都对两个链表排序，返回排序后的链表，归并后得到最后所有链表的排序结果
    注意：
    当我将链表A和B传入排序方法时，因为A和B其实是指向排序链表的一个引用，所以传入方法里的A和B没有任何数据！
    切记！不要将对JAVA类的引用作为实参，如果想将函数的返回值作为实参，直接将函数作为参数
对于基本数据类型、String，因为是复制值不是指向数据区，所以引用也可以作为实参

• 堆

  堆这种数据结构的好处在于，返回最值的效率很高

将所有头节点加入堆后，每次取堆中最小节点，再把最小节点的next节点加入堆。
当堆为空时，完成了对所有链表的排序

代码

• 归并

  public ListNode mergeKLists(List<ListNode> lists) {  
          // write your code here
          if(lists.size() == 0) {
              return null;
          }
  		return  myMerge(lists);
      }
  
  	private ListNode myMerge(List<ListNode> lists) {
  		if(lists.size() == 1) {
  			return lists.get(0);		// 递归终止条件
  		}
  		
  		int mid = lists.size() / 2;
  		
  		return mySort(myMerge(lists.subList(0, mid)), myMerge(lists.subList(mid, lists.size())));
  	}
  	
  	private ListNode mySort(ListNode left, ListNode right) {
  		ListNode head;
  		ListNode listNode;
  		ListNode nextNode;
  		
  		// init ListNode
  		if(left == null && right == null) {
  			return null;
  		}else {
  			if(left == null) {
  				return right;
  			}else if (right == null) {
  				return left;
  			}else {
  				if(left.val <= right.val) {
  					listNode = new ListNode(left.val);
  					head = listNode;
  					left = left.next;
  				}else {
  					listNode = new ListNode(right.val);
  					head = listNode;
  					right = right.next;
  				}
  			}
  		}
  		
  		// fill ListNode
  		while(left != null && right != null) {
  			if(left.val <= right.val) {
  				nextNode = new ListNode(left.val);
  				left = left.next;
  			}else {
  				nextNode = new ListNode(right.val);
  				right = right.next;
  			}
  			listNode.next = nextNode;
  			listNode = nextNode;
  		}
  		if(left == null) {
  			while(right != null) {
  				nextNode = new ListNode(right.val);
  				right = right.next;
  				listNode.next = nextNode;
  				listNode = nextNode;
  			}
  		}else if(right == null) {
  			while(left != null) {
  				nextNode = new ListNode(left.val);
  				left = left.next;
  				listNode.next = nextNode;
  				listNode = nextNode;
  			}
  		}else {
  			
  		}
  		
  		return head;
  	}

• 堆

  public ListNode mergeKLists(List<ListNode> lists) {  
          // write your code here
  		ListNode tmp;
  		ListNode head;
  		PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(new Comparator<ListNode>(){		// 匿名内部类实现一个比较器
  			public int compare(ListNode arg0, ListNode arg1) {
  				if(arg0.val < arg1.val) {
  					return -1;
  				}else if(arg0.val == arg1.val) {
  					return 0;
  				}else {
  					return 1;
  				}
  			}
  		});
  		
  		
  		// 初始化结果链表的头部节点
  		for(ListNode listNode : lists) {
  			if(listNode != null) {
  				priorityQueue.add(listNode);
  			}
  		}
  		ListNode listNode = priorityQueue.poll();
  		if(listNode.next != null) {
  			priorityQueue.add(listNode.next);
  		}
  		tmp = new ListNode(listNode.val);
  		head = tmp;
  		
  		// 每次取出当前优先队列的最小元素，如果最小元素所在的链表有next，加入next
  		// 当优先队列为空，则表示取完了所有链表里的元素
  		while(!priorityQueue.isEmpty()) {
  			listNode = priorityQueue.poll();
  			tmp.next = listNode;
  			tmp = tmp.next;
  			if(listNode.next != null) {
  				priorityQueue.add(listNode.next);
  			}
  		}
  		return head;
      }

考察点

• 归并
• 堆