需要解释 javascript 中的递归反向单链表代码

Question

我 console.log 每一行，看过很多关于它的 youtube 视频，但无法理解它。我需要一步一步了解发生了什么。

举个例子，我知道 return head 在 if 语句之后永远不会被调用，但它应该考虑到每次 newHead 被声明时它调用 head.next 作为reverseList(head) 中的新头应该导致 head.next === null.

下面是我的代码：

let headList = {
  value: 1,
  next: {
    value:2,
    next: {
      value:3,
      next: {
        value:4,
        next: {
          value:5,
          next: null
        }
      }
    }
  }
}

function reverseList(head) {
    if(head == null || head.next == null) {
        return head
    }

    newHead = reverseList(head.next);

    head.next.next = head;
    
    head.next = null;
    return newHead;

};

reverseList(headList)

Answer 1

return head 在 if 语句实际执行之后。

在你的函数体中，我们几乎立即递归地回调它，所以就像爬梯子一样，执行函数的第一部分:

    if(head == null || head.next == null) {
        return head
    }

    newHead = reverseList(head.next);```

我们每个人的脑袋：

Head 1 ↩
  Head 2 ↩
    Head 3 ↩
      Head 4 ↩

现在我们在 Head 4 并再次递归调用带有参数 { value: 5, next: null } 的函数，但这是我们最后一次执行递归，因为我们到达了函数的基本情况 - 函数参数满足 if 语句，它立即 returns 到 Head 4。

现在我们将向下爬回此调用堆栈，并在向下的过程中为每个头执行函数的第二部分。

 // newHead = reverseList(head.next); <-- Resuming from here on the way back

    head.next.next = head;
    
    head.next = null;
    return newHead;

现在冻结时间，我们在 Head 4，准备爬下调用堆栈！

由于我们将 head.next 作为参数传递给最后一个递归函数调用并原样返回，因此 head.next 和 newHead 指向完全相同的对象。

请记住，我们现在在 Head 4，所以 head.next.next = head 与 newHead.next = head 相同。这意味着 Head 4 现在在 Head 5 之后！函数 returns { value: 5, next: { value: 4, next: null }}.

让我们继续执行，现在我们在 Head 3。

我们需要写 head.next.next 而不是 newHead.next 的原因是因为在调用栈中我们需要附加 Head 3 对象到 Head 4.next 属性而不是 newHead.next（因为 newHead.next 已经指向 Head 4）。

head.next.next 就像在说'我想在我们开始执行功能时在我面前的脑袋前面。

由于 Head 3.next 引用 Head 4，head.next.next 将把 Head 3 放在 Head 4.next 属性中，这就是我们所需要的。

所以在下降的路上 Head 4 变成 Head 5.next，Head 3 变成 Head 4.next 等等

递归函数很难直观地掌握，所以我建议从更简单的函数开始，例如这里：Recursion in JavaScript Explained Using a freeCodeCamp Challenge。

需要解释 javascript 中的递归反向单链表代码

Need an explanation to a Recursive reversed singly linked list code in javascript

javascript

reverse

singly-linked-list

recursive-datastructures