维护不易，点赞再看，感谢支持
合并K个升序链表
题目描述
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
提示：
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
分析
这题合并多个链表，可以遍历当前有效的(不为null)链表头找到最小的那个，逐一插入到新的链表中。也可以从前往后两两合并链表，使用上面合并两个有序链表的方法。但是这两种需要比较的次数。时间复杂度都为O(n*k)其中n为节点总个数，K为链表个数。
进行优化主要有两种具体实现思路 ，一种就是利用一种排序每次找到最小的节点，而这种更适合堆排序动态维护。另一种就是利用类似归并的思想。将两两归并，最终归并为一个链表。从效率上看每个比较次数本来从k次由归并变成了log k，所以时间复杂度为O(nlogk);而合并具体操作也有直接迭代和递归两种方式，这里就使用迭代的方式。
实现代码为：
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==0)return null;
if(lists.length==1)return lists[0];
List<ListNode>nodes1=new ArrayList<ListNode>();
List<ListNode>nodes2=new ArrayList<ListNode>();
int i=0;//归并
for(;i<lists.length-1;i+=2)
{ nodes1.add(mergeTwoLists(lists[i],lists[i+1]));
}
if(i==lists.length-1)nodes1.add(lists[i]);
while (true) { for(i=0;i<nodes1.size()-1;i+=2) { nodes2.add(mergeTwoLists(nodes1.get(i), nodes1.get(i+1))); } if(i==nodes1.size()-1) nodes2.add(nodes1.get(nodes1.size()-1)); nodes1.clear(); nodes1.addAll(nodes2); nodes2.clear(); if(nodes1.size()==1)return nodes1.get(0);
} }
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1==null)return l2; if(l2==null)return l1; if(l1.val>l2.val)//l1更小 { ListNode team=l1; l1=l2; l2=team; } ListNode value=l1; while (l2!=null) { if(l1.next==null) { l1.next=l2;break; } else if (l1.next.val<l2.val) { l1=l1.next; } else { ListNode node=l1.next; l1=l1.next=l2; l2=node; //l1=l1.next; } } return value; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
当然这样编写对数组的利用比较差，每次重新赋值浪费一定效率，可以直接复用数组每次两两合并的时候赋值到对应位置。具体代码为：
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==0)return null;
if(lists.length==1)return lists[0];
int k=lists.length-1;
while (k>0) { int i; for(i=0;i<k;i+=2) { lists[i/2]=mergeTwoLists(lists[i], lists[i+1]); } if(i==k) { lists[i/2]=lists[i]; k=(k+1)/2; } else { k/=2; } } return lists[0]; }
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//此处省略
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
两两交换链表中的节点
分析：
本题的要求就是交换奇偶节点。不能直接交换值也就意味不能直接赋值要通过链表插入删除来实现。而具体的流程也很简单：
具体实现代码为：
public ListNode swapPairs(ListNode head) {
if(head==null)return head;
ListNode value=new ListNode(0);
value.next=head;
ListNode team=value;
ListNode first;
ListNode second;
while (team!=null&&team.next!=null) {
if(team.next.next==null) return value.next;
first=team.next; second=team.next.next; team.next=second; first.next=second.next; second.next=first; team=first;//team=team.next.next
}
return value.next;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
结语
原创不易，bigsai请你帮两件事帮忙一下:
-
star支持一下， 您的肯定是我在平台创作的源源动力。
-
微信搜索「bigsai」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。
记得关注、咱们下次再见！
文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。
原文链接：bigsai.blog.csdn.net/article/details/108553238