算法：链表题（持续更）
本人刷题时思考的几个解法，欢迎交流
力扣链接：合并 2 个有序链表
力扣链接：合并K个有序链表
目录
- 合并 2 个有序链表
- 合并 k 个有序链表
- K 个中 minNode
- 排序队列取minNode队头
- 手动实现的排序队列
- 优先级队列
- 分治：两个一组逐渐合并
合并 2 个有序链表
合并 2 个有序链表
操作模型：
for -> cur = min(list1 OR list2)
细节优化前：
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0);
ListNode p = dummy;
while(list1 != null || list2 != null){
if(list1 == null){
p.next = list2;
break;
} else if(list2 == null) {
p.next = list1;
break;
}
if(list1.val < list2.val){
p.next = list1;
list1 = list1.next;
} else {
p.next = list2;
list2 = list2.next;
}
p = p.next;
}
return dummy.next;
}
}
细节优化后：
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1 == null) return list2;
if(list2 == null) return list1;
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
ListNode p1 = list1;
ListNode p2 = list2;
while(p1 != null && p2 != null) {
if(p1.val < p2.val){
cur.next = p1;
p1 = p1.next;
} else {
cur.next = p2;
p2 = p2.next;
}
cur = cur.next;
}
cur.next = p1 != null ? p1 : p2;
return dummy.next;
}
}
合并 k 个有序链表
K 个中 minNode
每次迭代，比较 K 个链表头，求最小值 minNode，加入返回链表
直到迭代完所有链表
时间复杂度 O（K * N）
运行时间：210ms
操作模型：
for -> (cur = min(lists.forEach -> node))
优化细节前代码：
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null) return null;
if(lists.length == 0) return null;
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
ListNode min;
int minPos;
boolean keep = true;
while(keep){
keep = false;
minPos = 0;
min = lists[0];
for(int p = 0; p < lists.length; p++) {
if(lists[p] == null) continue;
if(keep != true) keep = true;
if(min == null || (lists[p]).val < min.val) {
min = lists[p];
minPos = p;
}
}
if(keep != true) break;
cur.next = min;
lists[minPos] = min.next;
cur = cur.next;
}
return dummy.next;
}
}
优化细节后：
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
ListNode minNd;
int minPos;
while(true){
minPos = -1;
minNd = null;
for(int i = 0; i < lists.length; i++) {
if(lists[i] == null) continue;
if(minNd == null || lists[i].val < minNd.val) {
minNd = lists[i];
minPos = i;
}
}
if(minPos == -1) break;
cur.next = minNd;
lists[minPos] = lists[minPos].next;
cur = cur.next;
}
return dummy.next;
}
}
排序队列取minNode队头
手动实现的排序队列
运行时间：216ms
class Solution {
static class SortedQueue {
private static final LinkedList<ListNode> list =
new LinkedList<>();
ListNode popHead() {
return list.removeFirst();
}
void sortedPut(ListNode insert){
if (insert == null) return;
int index = 0;
for (ListNode node : list) {
if (node.val >= insert.val){
list.add(index, insert);
return;
}
index++;
}
if (index != 0){
list.addLast(insert);
} else {
list.addFirst(insert);
}
return;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
for (ListNode node : list){
builder.append(node.val).append(" ");
}
return builder.toString();
}
}
}
未加嵌套的单次逻辑：
public ListNode mergeKLists(ListNode[] lists) {
ListNode dummy = new ListNode(0);
ListNode p = dummy;
SortedQueue queue = new SortedQueue();
p.next = queue.popHead();
if(p.next.next != null){
queue.sortedPut(p.next.next);
}
p = p.next;
}
加入嵌套、嵌套退出的条件：
while(queue.list.size() != 0){ ...... }
完整代码：
class Solution {
static class SortedQueue {
static final LinkedList<ListNode> list = new LinkedList<>();
ListNode popHead() {
return list.removeFirst();
}
void sortedPut(ListNode insert){
if (insert == null) return;
int index = 0;
for (ListNode node : list) {
if (node.val >= insert.val){
list.add(index, insert);
return;
}
index++;
}
if (index != 0){
list.addLast(insert);
} else {
list.addFirst(insert);
}
return;
}
}
public ListNode mergeKLists(ListNode[] lists) {
ListNode dummy = new ListNode(0);
ListNode p = dummy;
SortedQueue queue = new SortedQueue();
for(ListNode node : lists){
queue.sortedPut(node);
}
while(queue.list.size() != 0){
p.next = queue.popHead();
if(p.next.next != null){
queue.sortedPut(p.next.next);
}
p = p.next;
}
return dummy.next;
}
}
优先级队列
本质是小根堆，小根堆的根节点就是最小值，相比于我实现的队列，它的插入效率更高
运行时间：4ms
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
if (o1.val < o2.val) return -1;
else if (o1.val == o2.val) return 0;
else return 1;
}
});
ListNode dummy = new ListNode(0);
ListNode p = dummy;
for (ListNode node : lists) {
if (node != null) queue.add(node);
}
while (!queue.isEmpty()) {
p.next = queue.poll();
p = p.next;
if (p.next != null) queue.add(p.next);
}
return dummy.next;
}
}
分治：两个一组逐渐合并
运行时间：1ms
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0){
return null;
}
return spilt(lists , 0 , lists.length - 1);
}
public ListNode spilt(ListNode[] lists , int i , int j){
if(i == j){
return lists[i];
}
int m = (i + j) >>> 1;
ListNode left = spilt(lists , i , m);
ListNode right = spilt(lists , m+1 , j);
return mergeTwoLists(left, right);
}
public ListNode mergeTwoLists(ListNode p1, ListNode p2) {
ListNode s = new ListNode(-1, null);
ListNode p = s;
while (p1 != null && p2 != null) {
if (p1.val < p2.val) {
p.next = p1;
p1 = p1.next;
} else {
p.next = p2;
p2 = p2.next;
}
p = p.next;
}
p.next = p1 != null ? p1 : p2;
return s.next;
}
}