(leetcode)合并多条有序链表

题目

给定多条有序链表，合并返回一条链表

例如：

输入：

1->3->5

2->4->6

3->6->9

输出：

1->2->3->3->4->5->6->9

思路：

简化问题，用分治的思想将多条链表的合并转为两两合并

代码：

public class MergeSort1 {
	  public ListNode mergeKLists(ListNode[] lists) {
		return mergeKLists1(lists,0,lists.length-1);
		  
	  }
	  
	  //递归处理
	  private ListNode mergeKLists1(ListNode[] lists,int start,int stop) {
		  if(start==stop) return lists[start];
		  
		  int mid = (start+stop)/2;
		  
		  ListNode node1 = mergeKLists1(lists, start, mid);
		  ListNode node2 = mergeKLists1(lists, mid+1, stop);
		  return merge(node1, node2);
			  
	  }

	//两条有序链表合并
	  private ListNode merge(ListNode node1, ListNode node2){
	        if(node1 == null) return node2;
	        if(node2 == null) return node1;
	        
	        if(node1.val < node2.val){
	            node1.next = merge(node1.next, node2);
	            return node1;
	        }else{
	            node2.next = merge(node1, node2.next);
	            return node2;
	        }
	  }

}