《代码随想录》刷题笔记——链表篇【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)
目录
相关文章
|
23天前
|
前端开发 JavaScript Java
Java构建工具-maven的复习笔记【适用于复习】
这篇文档由「潜意识Java」创作,主要介绍Maven的相关知识。内容涵盖Maven的基本概念、作用、项目导入步骤、依赖管理(包括依赖配置、代码示例、总结)、依赖传递、依赖范围以及依赖的生命周期等七个方面。作者擅长前端开发,秉持“得之坦然,失之淡然”的座右铭。期待您的点赞、关注和收藏,这将是作者持续创作的动力! [个人主页](https://blog.csdn.net/weixin_73355603?spm=1000.2115.3001.5343)
34 3
|
23天前
|
存储 Java 开发者
【潜意识Java】深入详细理解分析Java中的toString()方法重写完整笔记总结,超级详细。
本文详细介绍了 Java 中 `toString()` 方法的重写技巧及其重要
46 10
【潜意识Java】深入详细理解分析Java中的toString()方法重写完整笔记总结,超级详细。
|
2月前
|
安全 Java 编译器
Kotlin教程笔记(27) -Kotlin 与 Java 共存(二)
Kotlin教程笔记(27) -Kotlin 与 Java 共存(二)
|
2月前
|
Java 开发工具 Android开发
Kotlin教程笔记(26) -Kotlin 与 Java 共存(一)
Kotlin教程笔记(26) -Kotlin 与 Java 共存(一)
|
3月前
|
Java 编译器 Android开发
Kotlin教程笔记(28) -Kotlin 与 Java 混编
Kotlin教程笔记(28) -Kotlin 与 Java 混编
56 2
|
2月前
|
Java 数据库连接 编译器
Kotlin教程笔记(29) -Kotlin 兼容 Java 遇到的最大的“坑”
Kotlin教程笔记(29) -Kotlin 兼容 Java 遇到的最大的“坑”
78 0
|
9月前
|
Java
使用Java代码打印log日志
使用Java代码打印log日志
337 1
|
Java BI API
在Java代码中打日志需要注意什么?
日志是什么?日志是你在代码运行时打印出来的一些数据和记录,是快速排查问题的好帮手,是撕逼和甩锅的利器!
726 0
|
缓存 Java 网络架构
别在 Java 代码里乱打日志了,这才是正确的打日志姿势!
别在 Java 代码里乱打日志了,这才是正确的打日志姿势!
175 0