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

Question

我已经

console.log

每一行，看过很多YouTube视频，但无法理解它。 我需要一步一步了解正在发生的事情。

举个例子，我知道 if 语句之后的

return head

永远不会被调用，但应该考虑到每次

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

语句，并且返回到

 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

指向完全相同的对象。

请记住，我们现在处于标题 4，因此

head.next.next = head

与

newHead.next = head

相同。这意味着

Head 4

现在在

Head 5

之后！函数返回

{ 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

等等

递归函数可能很难直观地掌握，因此我建议从更简单的函数开始，例如：使用 freeCodeCamp 挑战解释 JavaScript 中的递归。

Answer 2

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


// Simplistic approach, without recursion
function reverseLinkedList(lst) {
  let node = {...lst};
  let reversed = {value: node.value, next: null};
  
  while(node) {
    node = node.next;
    if (node) reversed = {value: node.value, next: {...reversed}};
  }
  
  return reversed;
}


const reversedHead = reverseLinkedList(headList);
console.log(reversedHead);

const origHead = reverseLinkedList(reversedHead);
console.log(origHead);