LeetCode 热题 HOT 100：链表专题

news/2024/5/17 20:01:38 标签: leetcode, 链表, 算法, 排序算法, 归并排序

LeetCode 热题 HOT 100：https://leetcode.cn/problem-list/2cktkvj/

文章目录

2. 两数相加

题目链接：https://leetcode.cn/problems/add-two-numbers/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

实现步骤：

  • 将两个链表看成是相同长度的进行遍历，如果一个链表较短则在前面补 0，比如：987 + 23 = 987 + 023 = 1010。
  • 每一位计算的同时需要考虑上一位的进位问题，而当前位计算结束后同样需要更新进位值。
  • 如果两个链表全部遍历完毕后，进位值为 1，则在新链表最前方添加节点。
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode p1 = l1, p2 = l2, q = pre;
        int sign = 0;
        while(p1 != null || p2 != null){
            int sum = 0;
            if(p1 == null){
                sum = p2.val + sign;
                p2 = p2.next;
            }else if(p2 == null){
                sum = p1.val + sign;
                p1 = p1.next;
            }else{
                sum = p1.val + p2.val + sign;
                p1 = p1.next;
                p2 = p2.next;
            }
            sign = sum >= 10 ? 1 : 0; // 修改标志位
            ListNode node = new ListNode(sum % 10);
            q.next = node;
            q = q.next;
        }
        if(sign == 1){
            ListNode node = new ListNode(1);
            q.next = node;
        }
        return pre.next;
    }
}

19. 删除链表的倒数第 N 个结点

题目链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode pre = new ListNode(0); // 伪头部节点
        pre.next = head;
        ListNode p, q;
        p = q = pre;
        int co = 0;
        while(q.next != null){ // 先让q指针先走n步，然后p指针再继续走
            if(++co > n){
                p = p.next;
            }
            q = q.next;
        }// 结束循环时，p指针指向倒数第N+1位
        p.next = p.next.next;
        // 注意避坑点：return head; 是存在问题的：当链表中只有一个元素时，p指针会进行删除后，head 还是指向原来的那个结点。
        return pre.next; 
    }
}

21. 合并两个有序链表

题目链接：https://leetcode.cn/problems/merge-two-sorted-lists/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode res = new ListNode(0);
        ListNode p = res;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                p.next = list1;
                list1 = list1.next;
            }else{
                p.next = list2;
                list2 = list2.next;
            }
            p = p.next;
        }
        p.next = list1 == null ? list2 : list1;
        return res.next;
    }
}

23. 合并 K 个升序链表

题目链接：https://leetcode.cn/problems/merge-k-sorted-lists/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode head = null;
        for(int i = 0; i < lists.length; i ++){
            head = mergeTwoLists(head, lists[i]);
        }
        return head;
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b){
        ListNode res = new ListNode(0);
        ListNode p = res;
        while(a!=null && b!=null){
            if(a.val < b.val){
                p.next = a;
                a = a.next;
            }else{
                p.next = b;
                b = b.next;
            }
            p = p.next;
        }
        p.next = a != null ? a : b;
        return res.next;
    }
}

141. 环形链表

题目链接：https://leetcode.cn/problems/linked-list-cycle/description/?envType=study-plan-v2&envId=top-100-liked

哈希表做法（时间复杂度较高）：

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null){
            return false;
        }
        Set<ListNode> set = new HashSet(); // set 记录结点的地址
        while(head.next != null){
            if(set.contains(head)){
                return true;
            }
            set.add(head);
            head = head.next;
        }
        return false;
    }
}

快慢指针做法1：

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null){
            return false;
        }
        ListNode slow, fast;
        slow = head;
        fast = head.next;
        // slow 每次向前走一步，fast 每次向前走两步（可以任意多步）
        // 当存在环时，fast 由于走得快，会发生扣圈的情况，且最终与 slow 相遇
        // 当不存在环时，fast 可能在某次循环后，发生当前位置为空，或下一位置为空的两种情况，当然由于走的快，最终会返回false。
        // 总之，循环的结束条件，要么出现环 slow == fast，要么 fast 先一步为空！ 
        while(slow != fast && fast != null && fast.next != null){
            // 注意：fast != null 要先于fast.next != null 来判断，以防止控制帧异常
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow == fast;
    }
}

快慢指针做法2（思路同下方“环形链表2”）：

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;

        while(true){
            if(fast==null || fast.next==null){
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
            if(slow==fast){
                return true;
            }
        }
    }
}

142. 环形链表 II

题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/?envType=study-plan-v2&envId=top-100-liked

哈希表做法（时间复杂度较高）：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        ListNode p = head;
        while(p!=null){
            if(set.contains(p)){
                return p;
            }
            set.add(p);
            p = p.next;
        }
        return null;
    }
}

快慢指针，实现思路如下：

  • 设 fast 每次走两个节点， slow 每次走一个节点。环外有 a 个结点，环内有 b 个结点。
  • 相遇时，fast 走了 f 步，slow 走了 s 步。
    ① f = 2s
    ② f = s + nb 表示 f 比 s 多走了 n*b 步，即 n 圈。这样表示的原因在于扣圈。
    化简得：f = 2nb, s = nb
  • 设刚开始 slow 指针从开始到环的入口要走 k 步：k = a + nb （n = 0,1,2,…）
  • 由于 s = n*b，即已经走了 n*b 步了，那么此时只需要再走 a 步即可回到链表入环的起点。
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while(true){
            if(fast == null || fast.next == null){
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        fast = head; // fast回到链表起点，与 slow 一同遍历 a 步
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

148. 排序链表

题目链接：https://leetcode.cn/problems/sort-list/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

使用优先队列模仿堆：

class Solution {
    public ListNode sortList(ListNode head) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> b.val-a.val); // 大顶堆
        while(head != null){
            queue.offer(head); // 从堆底插入
            head = head.next;
        }
        ListNode pre = new ListNode(0);
        while(!queue.isEmpty()){
            ListNode p = queue.poll(); // 出队列并调整堆
            p.next = pre.next; // 头插法倒序
            pre.next = p;
        }
        return pre.next;
    }
}

自顶向下归并排序1： 时间复杂度 O(nlogn)，空间复杂度O(logn)

class Solution {
    public ListNode sortList(ListNode head) {
        return mergeSort(head, null);
    }

    // 归并排序
    // 将头指针和尾指针之前的元素进行排序，初始尾指针为null，即最后一个节点的下一个空节点
    public ListNode mergeSort(ListNode head, ListNode tail){
        if(head == tail){
            return head;
        }
        if(head.next == tail){ // 隔离出来单独结点
            head.next = null;
            return head;
        }
        ListNode slow, fast;
        slow = fast = head;
        while(fast != tail){
            slow = slow.next;
            fast = fast.next;
            if(fast != tail){
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode l1 = mergeSort(head, mid); // 将 head 至 mid 之前的节点进行排序
        ListNode l2 = mergeSort(mid, tail); // 将 mid 至 tail 之前的节点进行排序
        return mergeList(l1, l2);
    }

    // 合并两个有序链表
    public ListNode mergeList(ListNode l1, ListNode l2){
        ListNode pre = new ListNode(0);
        ListNode p = pre;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                p.next = l1;
                l1 = l1.next;
            }else{
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        p.next = l1 == null ? l2:l1;
        return pre.next;
    }
}

参考链接：https://leetcode.cn/problems/sort-list/solutions/492301/pai-xu-lian-biao-by-leetcode-solution/?envType=featured-list&envId=2cktkvj%3FenvType%3Dfeatured-list&envId=2cktkvj

自顶向下归并排序2：

class Solution {
    public ListNode sortList(ListNode head) {
        return mergeSort(head);
    }
    
	// 归并排序
    public ListNode mergeSort(ListNode head){
        if(head==null || head.next==null){
            return head;
        }
        ListNode slow = head; // 快慢指针
        ListNode fast = head.next;

        while(fast!=null && fast.next!=null){ // 查询中间节点
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode mid = slow.next; // 断链
        slow.next = null;

        ListNode l1 = mergeSort(head);
        ListNode l2 = mergeSort(mid);
        return mergeList(l1, l2);
    }

	// 合并两个有序链表
    public ListNode mergeList(ListNode l1, ListNode l2){
        ListNode pre = new ListNode(0);
        ListNode p = pre;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                p.next = l1;
                l1 = l1.next;
            }else{
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        p.next = l1 == null ? l2:l1;
        return pre.next;
    }
}

自底向上排序： 时间复杂度 O(nlog)，空间复杂度O(n)

class Solution {
    public ListNode sortList(ListNode head) {
        ListNode pre = new ListNode(0);
        pre.next = head;

        int len = getLength(head); // 获取长度
        for(int step = 1; step < len; step *=2){ //依次将链表分块的长度分为：1，2，4...
            ListNode curr = pre.next;
            ListNode p = pre;
            // p 用于链接每次分块的链表，如：第一次循环链接分块长度为1的链表，然后链接分块长度为2的链表
            while(curr != null){
                ListNode h1 = curr; // 第一块链表的头
                ListNode h2 = spilt(h1, step); // 第二块链表的头
                curr = spilt(h2, step); // 下次while循环的头，也是给到h1
                // 合并第一二块链表，下次while循环合并第三四块链表....
                ListNode res = mergeList(h1, h2);
                // 将合并后的链表链接起来，并将指针移到链表的最后一个节点，以链接下次的链表
                p.next = res;
                while(p.next!=null){
                    p = p.next;
                }
            }
        }
        return pre.next;
    }

    // 分割链表，并返回后半段的链头
    public ListNode spilt(ListNode head, int step){
        if(head == null){
            return null;
        }
        ListNode p = head;
        for(int i = 1; i < step && p.next!=null; i ++){
            p = p.next;
        }
        ListNode right = p.next;
        p.next = null; // 切断连接
        return right;
    }

    // 求链表长度
    public int getLength(ListNode head){
        int co = 0;
        while(head!=null){
            co++;
            head = head.next;
        }
        return co;
    }

    // 合并两个升序链表
    public ListNode mergeList(ListNode l1, ListNode l2){
        ListNode pre = new ListNode(0);
        ListNode p = pre;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                p.next = l1;
                l1 = l1.next;
            }else{
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        p.next = l1 == null ? l2:l1;
        return pre.next;
    }
}

160. 相交链表

题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

实现步骤：

  • 设不是公共部分的节点数分别是 a、b，公共节点数为 n。
  • 如果有公共节点，则当 p1 遍历完 a+n 个节点时，再在另一个链表的头部遍历 b 个节点时，必相交。原因在于此时 p2 遍历了 b+n+a 个结点。
  • 如果没有公共节点部分，那么 p1 与 p2 经历了上文的步骤后，都会为 null， null==null 为 true。
    因此跳出循环，要么 null == null，要么都不为空找到了公共节点。
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA;
        ListNode p2 = headB;
        while(p1 != p2){
            p1 = p1 == null ? headB : p1.next;
            p2 = p2 == null ? headA : p2.next;
        }
        return p1;
    }
}

206. 反转链表

题目链接：https://leetcode.cn/problems/reverse-linked-list/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = new ListNode(0);
        ListNode p = head;
        while(p!=null){
            ListNode q = p.next;
            p.next = pre.next;
            pre.next = p;
            p = q;
        }
        return pre.next;
    }
}

234. 回文链表

题目链接：https://leetcode.cn/problems/palindrome-linked-list/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

class Solution {
    public boolean isPalindrome(ListNode head) {
        Deque<ListNode> stack = new LinkedList<>();
        ListNode p = head;
        while(p!=null){
            stack.push(p);
            p = p.next;
        }
        while(head != null){
            p = stack.pop();
            if(p.val != head.val){
                return false;
            }
            head = head.next;
        }
        return true;
    }
}

http://www.niftyadmin.cn/n/5015403.html

相关文章

4. 广播变量

4. 广播变量

一、分区规则&#xff08;DataStream Broadcast&#xff09;和广播变量&#xff08;Flink Broadcast&#xff09; 1.1 DataStream Broadcast&#xff08;分区规则&#xff09; ​ 分区规则是把元素广播给所有的分区&#xff0c;数据会被重复处理。 DataStream.broadcast()1.…
阅读更多...
第9节-PhotoShop基础课程-移动抓手缩放工具

第9节-PhotoShop基础课程-移动抓手缩放工具

文章目录 前言1. 移动工具1.移动工具1.自动选择&#xff08;图层和组&#xff09;2.显示变换控件 &#xff08;Shift 变换/ Ctrl 变换&#xff09;3.自由变换 Ctrl T &#xff08;Shift 变换/ Ctrl 变换&#xff09;4.对齐功能 2.画板工具 V1. 创建画板并作图2.导出画板 2.路…
阅读更多...
C++ 多线程 学习笔记

C++ 多线程 学习笔记

线程睡眠很稳定&#xff0c;但无线程睡眠不稳定 线程调用类方法&#xff1a; 有参数时调用方法&#xff1a; 当参数为引用时&#xff1a; 当同一资源被多个线程同时引用时&#xff0c;为防止资源抢占&#xff0c;使用mutex&#xff0c;互斥锁 头文件#include "mutex"…
阅读更多...
【群智能算法改进】一种改进的鹈鹕优化算法 IPOA算法[1]【Matlab代码#57】

【群智能算法改进】一种改进的鹈鹕优化算法 IPOA算法[1]【Matlab代码#57】

文章目录 【获取资源请见文章第5节&#xff1a;资源获取】1. 原始POA算法2. 改进后的IPOA算法2.1 Sine映射种群初始化2.2 融合改进的正余弦策略2.3 Levy飞行策略 3. 部分代码展示4. 仿真结果展示5. 资源获取 【获取资源请见文章第5节&#xff1a;资源获取】 1. 原始POA算法 此…
阅读更多...
关于C++的隐藏 (hidden)，重载(overload)，重写(override)小结。

关于C++的隐藏 (hidden)，重载(overload)，重写(override)小结。

关于隐藏 (hidden) 假如继承以后&#xff0c;子类出现父类同名函数&#xff0c; 即使参数的形式不同&#xff0c; 也会导致父类的函数隐藏&#xff0c; 不参与函数匹配&#xff0c;不能使用。 这个链接讲的不错。https://zhuanlan.zhihu.com/p/575423511 #include <iostrea…
阅读更多...
Linux信号量环形队列处理生产消费者模型

Linux信号量环形队列处理生产消费者模型

目录 一、信号量 1.1 信号量的概念 1.2 信号量的函数接口 1.2.1 sem_init&#xff08;&#xff09; 1.2.2 sem_destroy&#xff08;&#xff09; 1.2.3 sem_wait&#xff08;&#xff09;(P操作申请信号量) 1.2.4 sem_post&#xff08;&#xff09;(V操作增加信号量) 二…
阅读更多...
RK3568-mpp(Media Process Platform)媒体处理软件平台

RK3568-mpp(Media Process Platform)媒体处理软件平台

第一章 MPP 介绍 1.1 概述 瑞芯微提供的媒体处理软件平台（Media Process Platform，简称 MPP）是适用于瑞芯微芯片系列的通用媒体处理软件平台。 该平台对应用软件屏蔽了芯片相关的复杂底层处理，其目的是为了屏蔽不同芯片的差异，为使用者提供统一的视频媒体处理接口（Medi…
阅读更多...
构建可扩展的应用：六边形架构详解与实践

构建可扩展的应用：六边形架构详解与实践

面试题分享 云数据解决事务回滚问题 点我直达 2023最新面试合集链接 2023大厂面试题PDF 面试题PDF版本 java、python面试题 项目实战:AI文本 OCR识别最佳实践 AI Gamma一键生成PPT工具直达链接 玩转cloud Studio 在线编码神器 玩转 GPU AI绘画、AI讲话、翻译,GPU点亮…
阅读更多...
最新文章

Copyright @ 2022~2023