左神算法学习笔记 - 009【入门】单双链表及其反转-堆栈诠释

Weijian Duan

2025-02-13

【算法讲解009【入门】单双链表及其反转-堆栈诠释】 https://www.bilibili.com/video/BV1N94y1C7az/?share_source=copy_web&vd_source=939a5033dc1ec4f712d59a4a4042e169

复习记录一下之前的基本内容：Java 当中值传递的理解（堆栈结构）；单链表、双链表的反转（也从堆栈中理解一下整个过程）

按值传递还是按引用传递

这个经典的知识点，如果只从字面上去理解和记忆的话，非常容易混淆。比如，左神按照他的版本讲解完之后，评论区还是会有这样的问题：

java核心技术卷1这本书中，方法参数章节说java总是采用按值调用？

左神的解释：

传递时总是整出独立的一份，就认为是“按值传递”；传递时变量还指向老的内存地址，就认为是“引用传递”。“java总是采用按值调用”，这一句是说，哪怕按“引用传递”的变量，其实也是新的引用，这个新的引用和老的引用都指向同一个内存地址。举个例子，一个门牌上有内存地址，在传递时，总是新拷贝出新的门牌，但是新、老门牌上写的地址是一样的，指向内存的同一个区域。这就是所谓的“java总是采用按值调用”。
变量传递下去，所有的函数会不会改变同一个内存区域？根据这个来区分会比较好。不会改变，每次都是独立的一份，那就认为“按值传递”。会改变，那就认为“按引用传递”。

所以我们应该抛开所谓的字面说法，去理解问题的本质：

当调用方法的入参是基本类型或者 String 的时候，方法内部接到的参数是栈空间里的一份拷贝。学过 JVM 的内存结构就会知道，每个方法调用都是虚拟机栈里的一个栈帧。这就是所谓的传递值。
如果入参是对象类型的话，首先需要知道，对象类型的变量本身就是栈里的引用，而传递进去的时候，方法栈帧里保存的是一份引用的拷贝，两个引用都指向堆内存中的同一个对象。而有这个引用我们可以操作堆内存中的对象。因此我们可以说是「按引用传递」，也可以说我们在方法里得到了一个新的引用值，就是所谓的「Java 总是按引用传递」。

于是我们可以考虑一个场景：

f(b) 调用方法，其中 b 是一个对象引用

如果在方法内部：
  b' = null，其中 b' 是方法参数

外部的 b 会改变吗？

答案是不会的，因为底层做的事情就是把新的引用拷贝指向了 null，不会影响旧的引用的。

单链表和双链表的反转

单双链表的定义很简单：

单链表：节点定义中有值 val 和下一个节点引用 next，其中最后一个节点的 next 为 null
双链表：在单链表的基础上，每一个节点还有上一个节点的引用，其中第一个节点 prev 为 null

在理解值传递和堆栈概念的基础上，最简单的题目就是反转单双链表了。

由于非常简单直接看代码，需要理解的就是方法的抽象就是 f(head) -> new_head，即我们传入旧的链表头，然后方法处理好反转之后，返回新的链表头：

Leetcode: 反转单链表

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode next = null;
        
        while (head != null) {
            next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}

一些注意点：

prev 和 next 初始化就分行写，语法上一行不好写
注意处理是一个 while 循环，即「当 head 还没有来到末尾的时候」就进行反转
最终head 来到了 null 了，返回的是 prev 节点，它就是 new_head。

双链表反转代码（没有 leetcode 就看一下代码）

唯一的不一样就是，每次反转操作的时候 head 的 last 也要处理一下，指向 next。