题设
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
public ListNode mergeKLists(ListNode[] lists){
要点
- 链表合并
- 迭代
- 归并排序
对已经有序的k个链表进行合并，有两种思路：
1、对lists中的每2个链表进行merge(merge可以直接采用归并排序的merge方法)，形成新的链表；重复此操作，直到链表数组中的元素只有一个。这种迭代的方法最后跑出来的时间较长；
public ListNode mergeKLists(ListNode[] lists){
/*
1、迭代的方法
*/
/*
int len = lists.length;
if(len == 0 || lists == null)
return null;
if(len == 1)
return lists[0];
System.out.println("len: " + len);
ListNode[] newList;
while(len > 1){
if(len % 2 != 0)
newList = new ListNode[len / 2 + 1];
else
newList = new ListNode[len / 2];
for(int i = 0;i < newList.length;i++){
if(i * 2 + 1 < len)
newList[i] = mergeForList(lists[i * 2] , lists[i * 2 + 1]);
else
newList[i] = lists[i * 2];
}
lists = newList;
System.out.println(lists.length + "kkk");
if(len % 2 == 0)
len /= 2;
else
len = len / 2 + 1;
}
return lists[0];
}
2、递归的方法。其实仔细观察可得，对数组中每两个链表进行归并，生成新链表并重复的过程，类似归并排序中递归分解的过程。我们要做的是把一个链表数组递归分解直到每一个链表元素，然后进行merge即可，这其实就是对一系列的有序链表做归并排序(传统的归并排序中，数组内的元素为int，而这里改成了有序链表而已)
public ListNode mergeKLists(ListNode[] lists){
/*
2、递归的方法
其实仔细观察可得，对数组中每两个链表进行归并，生成新链表并重复的过程，类似归并排序中递归分解的过程
我们要做的是把一个链表数组递归分解直到每一个链表元素，然后进行merge即可
*/
int len = lists.length;
if(len == 0 || lists == null)
return null;
if(len == 1)
return lists[0];
return mergeSortForKList(lists , 0 , len - 1);
}
/*
k个有序链表的递归分解
@list： 待合并的有序链表集合
@low ： 此次分解的低位
@high： 此次分解的高位
与归并算法思路相同，先对链表数组进行分解，直到区间内只剩下一个元素，进行merge
*/
public ListNode mergeSortForKList(ListNode[] list , int low , int high){
if(low == high)
return list[low];
if(low < high){
int middle = (low + high) >> 1;
ListNode left = mergeSortForKList(list, low, middle);
ListNode right = mergeSortForKList(list, middle + 1, high);
return mergeForList(left, right);
}
return null;
}
/*
有序链表的归并算法
@leftHead： 拆分后左链表头指针；
@rightHead：拆分后右链表头指针；
初始两个链表指针leftHead和rightHead都在头部。比较其对应的val值，将值小的接入新的链表，同时移动链表指针
一个有序链表遍历完成后，需要将另一个链表剩下的元素接入新的链表
*/
public ListNode mergeForList(ListNode leftHead , ListNode rightHead){
// 存储归并后新的有序链表，最后返回newHead.next
ListNode newHead = new ListNode(-1);
ListNode tempHead = newHead;
// 比较val大小，移动链表并更新保存结果的有序链表
while(leftHead != null && rightHead != null){
if(leftHead.val < rightHead.val){
tempHead.next = new ListNode(leftHead.val);
leftHead = leftHead.next;
tempHead = tempHead.next;
}
else{
tempHead.next = new ListNode(rightHead.val);
rightHead = rightHead.next;
tempHead = tempHead.next;
}
}
// 将未遍历完的链表接入
if(leftHead == null)
tempHead.next = rightHead;
else
tempHead.next = leftHead;
// 返回归并后的有序链表
return newHead.next;
}
