算法——链表(二)

在这里插入图片描述

T04BF
👋专栏: 算法|JAVA|MySQL|C语言
🫵 小比特大梦想

此篇文章与大家分享链表专题的第二篇,大部分知识在第一篇中已经呈现
对于归并排序在我个人主页专栏 <排序> 有详细的介绍
如果有不足的或者错误的请您指出!

4.合并K个升序链表

题目:合并k个升序链表

4.1解析

如果是合并两个升序列表,那么我们肯定都是不陌生的
但是这道题要我们做的是合并k个,那么我们就可以两个两个合并,将合并完的再和第三条合并,因此我们最容易想到的暴力解法就是简单的两两排序形成新链表,再与第三链表进行再次排序,但是时间复杂度太高了,达到O(n*k^2),我们有两种优化方法

4.1.1利用优先级进行优化

我们之前在合并两个有序链表的时候,是用两个变量分别遍历两个链表,每次将二者中最小的那一个插入到新链表中
那么我们合并k个其实也是如此,每次比较出k个节点中较小的那一个
那么问题就是这么比较k个节点呢?? 我们可以利用优先级队列,建立小根堆,那么最小的元素一定是堆顶元素,这样每次将堆顶元素插入新链表即可.此时时间复杂度就降到O(n k logk)

优化1题解

class Solution {public ListNode mergeKLists(ListNode[] lists) {PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);for(ListNode node : lists){if(node != null){queue.offer(node);}}ListNode newHead = new ListNode(0);ListNode cur = newHead;while(!queue.isEmpty()){ListNode tmp = queue.peek();cur.next = queue.poll();cur = cur.next;if(tmp.next != null){queue.offer(tmp.next);}}return newHead.next;}
}

4.1.2归并排序进行优化

我们之前说过,两两合并我们是熟悉的,而归并排序恰好就是两两进行排序,那么我们就可以直接利用归并排序,再合并的过程中对两个链表进行合并,时间复杂度同样为O(n k logk)

优化2题解

    public ListNode mergeKLists(ListNode[] lists) {ListNode ret =  merge(lists, 0, lists.length-1);return ret;}private ListNode merge(ListNode[] lists,int left,int right){if(left >  right){return null;}if(left == right){return lists[left];}int mid = left + (right - left) / 2;ListNode l1 = merge(lists,left,mid);ListNode l2 = merge(lists,mid+1,right);return mergeTwoList(l1,l2);}private ListNode mergeTwoList(ListNode l1,ListNode l2){if(l1 == null){return l2;}if(l2 == null){return l1;}ListNode cur1 = l1;ListNode cur2 = l2;ListNode newHead = new ListNode(0);ListNode cur = newHead;while(cur1 != null && cur2 != null){if(cur1.val > cur2.val){cur.next = cur2;cur2 = cur2.next;}else{cur.next = cur1;cur1 = cur1.next;}cur = cur.next;} while(cur1 != null){cur.next = cur1;cur1 = cur1.next;cur = cur.next;}while(cur2 != null){cur.next = cur2;cur2 = cur2.next;cur = cur.next;}return newHead.next;}

5.k个一组翻转链表

题目:k个一组翻转链表

5.1解析

思路比较明确,首先需要求出你需要翻转多少对.因为题目要求不够k个节点的不翻转
接着对这几对进行翻转即可
有一点细节问题就是:
在这里插入图片描述
我们是引入"虚拟头结点",每次用cur遍历k个节点,将k个节点依次翻转插入newHead后面,因此我们针对每一组进行翻转的时候,都要有一个newHead,这个newHead就是我们要翻转的这一组的前一个节点;第一组的newHead就是我们引入的newHead,而后面的实际上就是上一组的第一个节点(因为翻转后他就是这一组的最后一个节点)

5.2题解

class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode cur = head;int n = 0;while(cur != null){n++;cur = cur.next;}n /= k;ListNode newHead = new ListNode(0,head);ListNode prev = newHead;cur = head;for(int i = 0; i < n; i++){ListNode tmp = cur;for(int j = 0; j < k; j++){ListNode t = cur.next;cur.next = prev.next;prev.next = cur;cur = t;}prev = tmp;}prev.next = cur;//将后面不需要翻转的插到后面去return newHead.next;}
}