算法系列--链表刷题(二)（上）
https://developer.aliyun.com/article/1480808?spm=a2c6h.13148508.setting.14.5f4e4f0e08yH7p
4.合并 K 个升序链表（hard）
链接:
https://leetcode.cn/problems/merge-k-sorted-lists/description/
分析:
思路一:利用优先级队列
其实本题和合并两个有序链表很相似,可以看做是上一题的plus版本
虽然这里是合并K个有序链表,但是我们可以借鉴合并两个有序链表的思路,`创建一个傀儡节点,找到两个链表节点的最小值,依次插入到傀儡节点之后
这里的难点在于如果只有两个节点,我们可以直接比较,但是现在有K个节点,如何快速地找到K个节点的最小值呢?使用优先级队列,利用优先级队列将K个链表的头结点存入到优先级队列之中,由于默认是小根堆,所以堆顶元素就是K个链表头结点的最大值,将其插入到傀儡节点之后,更新傀儡节点,然后插入堆顶节点的下一个节点,接着判断最小值,重复上述过程
手写:
代码:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeKLists(ListNode[] lists) { PriorityQueue<ListNode> heap = new PriorityQueue<>((o1,o2) ->o1.val - o2.val); ListNode ret = new ListNode(0); ListNode phead = ret; for(ListNode head : lists)// 将链表的头结点存入堆中 if(head != null) heap.offer(head); while(!heap.isEmpty()) { ListNode tmp = heap.poll(); phead.next = tmp; phead = tmp; if(tmp.next != null) heap.offer(tmp.next);// 注意下一个节点可能为空 } return ret.next; } }
思路二:利用
归并的思想
其实这道题非常符合分治归并的思想,题目相当于给了我们一个比较特殊的数组(数组的元素是链表),实际上最重要完成的工作就是对这K个元素进行从小到大的排序,既然是排序我们就可以使用归并的思想,为什么想到归并呢?这是经过分析得到的,实际上我们是对一个一个的链表进行合并+排序操作的,这一步其实就是归并中分解到最小单元,开始回并的过程啊!所以可以使用归并的思想解决
代码:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeKLists(ListNode[] lists) { if(lists == null || lists.length == 0) return null; // 采用归并的思想解决 return merge(lists,0,lists.length-1); } public ListNode merge(ListNode[] lists,int left,int right) { // 递归出口 if(left >= right) return lists[left]; int mid = (left + right) /2; ListNode l1 = merge(lists,left,mid); ListNode l2 = merge(lists,mid + 1,right); return mergeTwoLists(l1,l2); } // 合并两个有序链表 public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // 递归 if(list1 == null) return list2; if(list2 == null) return list1; if(list1.val < list2.val) { list1.next = mergeTwoLists(list1.next,list2); return list1; }else { list2.next = mergeTwoLists(list2.next,list1); return list2; } } }
5.K个⼀组翻转链表
链接:
https://leetcode.cn/problems/reverse-nodes-in-k-group/description/
分析:
本题采用模拟的思想,具体的模拟策略如下:
- 求出要反转多少个长度为K的链表–n
- 翻转n次即可
代码:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseKGroup(ListNode head, int k) { // 求需要翻转的组数n int cnt = 0; ListNode tmp = head; while(tmp != null) { cnt++; tmp = tmp.next; } int n = cnt / k; // 开始进行翻转 ListNode ret = new ListNode(0); ListNode phead = ret; ListNode cur = head; for(int i = 0; i < n; i++) { ListNode prev = cur;// 保存当前翻转链表的头结点 for(int j = 0; j < k; j++) { ListNode curnext = cur.next; cur.next = phead.next; phead.next = cur; cur = curnext; } phead = prev;// 每翻转完一组就更新phead } phead.next = cur; return ret.next; } }
