leetcode_【21】合并两个有序链表
leetcode_【21】合并两个有序链表
https://leetcode-cn.com/problems/merge-two-sorted-lists/
1.题目描述
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:
1->2->4, 1->3->4
输出:
1->1->2->3->4->4
2.解题思路
注:该题与剑指offer-[16]题一致,还可以用递归。
- (1) 判断是否有空链表,如果有则直接返回另一个不为空有序链表
- (2) 依次判断是否有对应链表大小,小的加入res链表,并移动
3.代码
/**
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1==null &&l2!=null)
return l2;
if(l2 == null && l1!=null)
return l1;
ListNode res = new ListNode(-1);
ListNode ans = res;
while(l1!=null&&l2!=null){
//哪个小添加哪个
if(l1.val>l2.val){
res.next = new ListNode(l2.val);
l2 = l2.next;
res = res.next;
}else{
res.next = new ListNode(l1.val);
l1 = l1.next;
res = res.next;
}
}
//将剩下的没便利完的加入
while(l1!=null){
res.next = new ListNode(l1.val);
l1 = l1.next;
res = res.next;
}
while(l2!=null){
res.next = new ListNode(l2.val);
l2 = l2.next;
res = res.next;
}
return ans.next;
}
}
4.提交记录
【合并两个有序链表】【合并K个排序链表】
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAzNfRHLGZkRGZkRfJ3bs92YsYTMfVmepNHL4tGVNJTVU50MFpHW4Z0MMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnLwczMzAjNyYTM0AzNwkTMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
leetcode_【23】合并K个排序链表
leetcode_【23】合并K个排序链表
https://leetcode-cn.com/problems/merge-k-sorted-lists/
1.题目描述
合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出:
1->1->2->3->4->4->5->6
2.解题思路
方法1:方法2:
- (1)利用priorityQueue的性质,每放一个数字进去就给你从小到大排好序了
- (2)队列的性质是先进先出,故依次poll出来就是从小到大的顺序,将该数值放到listNode里面即可。
- 借用合并两个链表的代码,依次将list[]分成两部分,在分别合并,执行用时为6ms
3.代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode res = new ListNode(-1);
ListNode ans = res;
PriorityQueue<Integer> queue = new PriorityQueue<>();
//将所有节点的值放到一个queue里面从小到大排好序
for(int i = 0;i< lists.length;i++){
while(lists[i]!=null){
queue.add(lists[i].val);
lists[i] = lists[i].next;
}
}
//依次建立链表
while(queue.size()!=0){
res.next = new ListNode(queue.poll());
res = res.next;
}
return ans.next;
}
}
方法2:
public ListNode mergeKLists(ListNode[] lists){
if(lists.length == 0)
return null;
if(lists.length == 1)
return lists[0];
if(lists.length == 2){
return mergeTwoLists(lists[0],lists[1]);
}
//将一半的链表放到l1里面
int mid = lists.length/2;
ListNode[] l1 = new ListNode[mid];
for(int i = 0; i < mid; i++){
l1[i] = lists[i];
}
//将一半的链表放到l2里面
ListNode[] l2 = new ListNode[lists.length-mid];
for(int i = mid,j=0; i < lists.length; i++,j++){
l2[j] = lists[i];
}
//递归实现多个链表的排序
return mergeTwoLists(mergeKLists(l1),mergeKLists(l2));
}
//递归方式实现两个链表排序
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode head = null;
if (l1.val <= l2.val){
head = l1;
head.next = mergeTwoLists(l1.next, l2);
} else {
head = l2;
head.next = mergeTwoLists(l1, l2.next);
}
return head;
}