《代码随想录》刷题笔记——链表篇【java实现】

简介: 《代码随想录》刷题笔记——链表篇【java实现】

链表节点定义

public class ListNode {
    // 结点的值
    int val;
    // 下一个结点
    ListNode next;
    // 节点的构造函数(无参)
    public ListNode() {
    }
    // 节点的构造函数(有一个参数)
    public ListNode(int val) {
        this.val = val;
    }
    // 节点的构造函数(有两个参数)
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

*移除链表节点

题目链接:https://leetcode.cn/problems/reverse-linked-list/

【思路】

有时候增加一个虚拟节点,可以让后面的操作都一致

public static ListNode removeElements(ListNode head, int val) {
    if (head == null) {
        return null;
    }
    // 增加一个虚拟节点
    ListNode virtualNode = new ListNode();
    virtualNode.next = head;
    ListNode cur = virtualNode;
    ListNode next = cur.next;
    while (next != null) {
        if (next.val == val) {
            cur.next = next.next;
        } else {
            cur = next;
        }
        next = cur.next;
    }
    return virtualNode.next;
}

*反转链表

双指针

  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

public static ListNode reverseList(ListNode head) {
    ListNode cur = head;
    ListNode pre = null;
    ListNode temp = null;
    while (cur != null) {
        temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}

递归法

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

这里的逻辑和双指针法的逻辑是一样的,只是实现方式是递归,那为什么空间复杂度更高呢?

答:因为递归本质上是一种函数调用,在每一次递归调用时,都会在函数栈中分配一段内存空间来保存函数的局部变量、返回地址以及参数等信息。因此,递归实现相对于循环实现的空间复杂度更高,会占用更多的内存空间。尤其是在递归深度较大的情况下,可能会导致栈溢出等问题。而使用循环实现通常不需要使用额外的栈空间,因此循环实现的空间复杂度比递归实现要低

public static ListNode reverseList1(ListNode head) {
    return reverse(null, head);
}
public static ListNode reverse(ListNode pre, ListNode cur) {
    if (cur != null) {
        ListNode temp = cur.next;
        cur.next = pre;
        pre = reverse(cur, temp);
    }
    return pre;
}

*两两交换链表中的节点

https://leetcode.cn/problems/swap-nodes-in-pairs/

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

public static ListNode swapPairs(ListNode head) {
    // 如果链表中没有元素 或者 只有一个元素,直接返回就行
    if (head == null || head.next == null) {
        return head;
    }
    // 增加一个虚拟头节点
    ListNode virtualNode = new ListNode();
    virtualNode.next = head;
    ListNode last = virtualNode;
    ListNode cur = head;
    ListNode next = cur.next;
    ListNode temp = null;
    while (next != null) {
        // 交换
        temp = next.next;
        cur.next = next.next;
        next.next = cur;
        last.next = next;
        // 指针移动到新的位置
        last = cur;
        cur = temp;
        if (cur != null) {
            next = cur.next;
        } else {
            break;
        }
    }
    return virtualNode.next;
}

*删除链表的倒数第N个节点

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/submissions/

快慢指针法

/**
 * 让快指针比慢指针先移动 n 步
 *
 * @param head
 * @param n
 * @return
 */
public static ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode virtual = new ListNode();
    virtual.next = head;
    // 让快指针先移动到n个节点
    ListNode fast = virtual;
    for (int i = 0; i < n; i++) {
        if (fast.next != null) {
            fast = fast.next;
        }
    }
    // slow和fast一起移动,等fast到达最后一个节点的时候,slow也就到达了要删除的节点前面的节点
    ListNode slow = virtual;
    while (fast.next != null) {
        slow = slow.next;
        fast = fast.next;
    }
    // 执行删除操作
    slow.next = slow.next.next;
    return virtual.next;
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

*链表相交

https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

注意点

并不是判断val相等,而是hashcode相等

暴力求解

直接两重循环,循环两个链表

  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)

进阶解法

利用题目中的信息,已经是链表的尾部才有可能相交,可以先让一条链表前进 两条链表长度差值 的位置,最后再两条链表一起前进

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode cur1 = headA;
    ListNode cur2 = headB;
    int sizeA = 0;
    int sizeB = 0;
    // 统计链表A的长度
    while (cur1 != null) {
        sizeA += 1;
        cur1 = cur1.next;
    }
    // 统计链表B的长度
    while (cur2 != null) {
        sizeB += 1;
        cur2 = cur2.next;
    }
    // 回到初始位置
    cur1 = headA;
    cur2 = headB;
    // 先让元素较多的链表的指针移动一段距离
    if (sizeA > sizeB) {
        // 链表A的元素较多,先走一段距离
        for (int i = 0; i < (sizeA - sizeB); i++) {
            cur1 = cur1.next;
        }
    } else if (sizeA < sizeB) {
        for (int i = 0; i < (sizeB - sizeA); i++) {
            cur2 = cur2.next;
        }
    }
    // 两个链表同时走动
    while (cur1 != null && cur2 != null) {
        // 注意,需要的是hash值
        if (cur1.hashCode() == cur2.hashCode()) {
            return cur1;
        }
        cur1 = cur1.next;
        cur2 = cur2.next;
    }
    return null;
}
  • 时间复杂度:O(n + m)
  • 空间复杂度:O(1)

*环形链表

https://leetcode.cn/problems/linked-list-cycle-ii/

public static ListNode detectCycle1(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode slow = head;
    ListNode fast = head;
    ListNode node2 = null;
    // 先找到相交点
    while (slow != null && fast.next != null) {
        // slow移动一步
        slow = slow.next;
        // fast移动两步
        fast = fast.next.next;
        if (slow.hashCode() == fast.hashCode()) {
            // slow 和 fast相交
            node2 = slow;
            // 让node1从起点出发,node2从相交点出发,当node1和node2相交的时候,相交时的节点即环的入口
            ListNode node1 = head;
            while (true) {
                if (node1.hashCode() == node2.hashCode()) {
                    return node1;
                } else {
                    node1 = node1.next;
                    node2 = node2.next;
                }
            }
        }
    }
    return null;
}
  • 时间复杂度: O(n)。因为快慢指针相遇前,指针走的次数小于链表长度;快慢指针相遇后,两个node指针走的次数也小于链表长度,因此走的总次数小于 2n
  • 空间复杂度: O(1)
目录
相关文章
|
28天前
|
前端开发 JavaScript Java
Java构建工具-maven的复习笔记【适用于复习】
这篇文档由「潜意识Java」创作,主要介绍Maven的相关知识。内容涵盖Maven的基本概念、作用、项目导入步骤、依赖管理(包括依赖配置、代码示例、总结)、依赖传递、依赖范围以及依赖的生命周期等七个方面。作者擅长前端开发,秉持“得之坦然,失之淡然”的座右铭。期待您的点赞、关注和收藏,这将是作者持续创作的动力! [个人主页](https://blog.csdn.net/weixin_73355603?spm=1000.2115.3001.5343)
35 3
|
6天前
|
JavaScript NoSQL Java
接替此文【下篇-服务端+后台管理】优雅草蜻蜓z系统JAVA版暗影版为例-【蜻蜓z系列通用】-2025年全新项目整合搭建方式-这是独立吃透代码以后首次改变-独立PC版本vue版搭建教程-优雅草卓伊凡
接替此文【下篇-服务端+后台管理】优雅草蜻蜓z系统JAVA版暗影版为例-【蜻蜓z系列通用】-2025年全新项目整合搭建方式-这是独立吃透代码以后首次改变-独立PC版本vue版搭建教程-优雅草卓伊凡
144 96
接替此文【下篇-服务端+后台管理】优雅草蜻蜓z系统JAVA版暗影版为例-【蜻蜓z系列通用】-2025年全新项目整合搭建方式-这是独立吃透代码以后首次改变-独立PC版本vue版搭建教程-优雅草卓伊凡
|
28天前
|
存储 Java 开发者
【潜意识Java】深入详细理解分析Java中的toString()方法重写完整笔记总结,超级详细。
本文详细介绍了 Java 中 `toString()` 方法的重写技巧及其重要
49 10
【潜意识Java】深入详细理解分析Java中的toString()方法重写完整笔记总结,超级详细。
|
1月前
|
SQL Java 数据库连接
如何在 Java 代码中使用 JSqlParser 解析复杂的 SQL 语句?
大家好,我是 V 哥。JSqlParser 是一个用于解析 SQL 语句的 Java 库,可将 SQL 解析为 Java 对象树,支持多种 SQL 类型(如 `SELECT`、`INSERT` 等)。它适用于 SQL 分析、修改、生成和验证等场景。通过 Maven 或 Gradle 安装后,可以方便地在 Java 代码中使用。
239 11
|
1月前
|
JSON Java 数据挖掘
利用 Java 代码获取淘宝关键字 API 接口
在数字化商业时代,精准把握市场动态与消费者需求是企业成功的关键。淘宝作为中国最大的电商平台之一,其海量数据中蕴含丰富的商业洞察。本文介绍如何通过Java代码高效、合规地获取淘宝关键字API接口数据,帮助商家优化产品布局、制定营销策略。主要内容包括: 1. **淘宝关键字API的价值**:洞察用户需求、优化产品标题与详情、制定营销策略。 2. **获取API接口的步骤**:注册账号、申请权限、搭建Java开发环境、编写调用代码、解析响应数据。 3. **注意事项**:遵守法律法规与平台规则,处理API调用限制。 通过这些步骤,商家可以在激烈的市场竞争中脱颖而出。
|
2月前
|
安全 Java 编译器
深入理解Java中synchronized三种使用方式:助您写出线程安全的代码
`synchronized` 是 Java 中的关键字,用于实现线程同步,确保多个线程互斥访问共享资源。它通过内置的监视器锁机制,防止多个线程同时执行被 `synchronized` 修饰的方法或代码块。`synchronized` 可以修饰非静态方法、静态方法和代码块,分别锁定实例对象、类对象或指定的对象。其底层原理基于 JVM 的指令和对象的监视器,JDK 1.6 后引入了偏向锁、轻量级锁等优化措施,提高了性能。
74 3
|
2月前
|
前端开发 Java 测试技术
java日常开发中如何写出优雅的好维护的代码
代码可读性太差,实际是给团队后续开发中埋坑,优化在平时,没有那个团队会说我专门给你一个月来优化之前的代码,所以在日常开发中就要多注意可读性问题,不要写出几天之后自己都看不懂的代码。
78 2
|
2月前
|
Java 数据库连接 编译器
Kotlin教程笔记(29) -Kotlin 兼容 Java 遇到的最大的“坑”
Kotlin教程笔记(29) -Kotlin 兼容 Java 遇到的最大的“坑”
82 0
|
8月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表