算法系列--链表刷题(二)(下)

简介: 算法系列--链表刷题(二)(下)

算法系列--链表刷题(二)(上)

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/

分析:

本题采用模拟的思想,具体的模拟策略如下:

  1. 求出要反转多少个长度为K的链表–n
  2. 翻转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;
    }
}


目录
相关文章
|
2天前
|
存储 缓存 算法
数据结构与算法⑦(第二章收尾)带头双向循环链表的实现(下)
数据结构与算法⑦(第二章收尾)带头双向循环链表的实现
4 0
|
2天前
|
存储 算法
数据结构与算法⑦(第二章收尾)带头双向循环链表的实现(上)
数据结构与算法⑦(第二章收尾)带头双向循环链表的实现
10 0
|
2天前
|
算法 搜索推荐 索引
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(下)
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题
5 0
|
2天前
|
算法 程序员 索引
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(中)
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题
12 0
|
2天前
|
算法 C语言 C++
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(上)
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题
12 0
|
2天前
|
算法 测试技术
数据结构与算法⑤(第二章OJ题,上)前五道链表面试题(下)
数据结构与算法⑤(第二章OJ题,上)前五道链表面试题
8 0
|
2天前
|
算法
数据结构与算法⑤(第二章OJ题,上)前五道链表面试题(上)
数据结构与算法⑤(第二章OJ题,上)前五道链表面试题
9 0
|
2天前
|
存储 算法 索引
数据结构与算法④(第二章下)链表概念+单链表的实现
数据结构与算法④(第二章下)链表概念+单链表的实现
7 0
|
7天前
|
存储 算法 容器
算法刷题小技巧【持续补充~】
算法刷题小技巧【持续补充~】
9 2
|
7天前
|
存储 算法 Java
数据结构与算法 数组和链表
数据结构与算法 数组和链表
12 0