从反转链表到执行上下文

最近在leetcode刷到了经典的题目----反转链表，其中有两种常规的解法：迭代法(双指针，尾接法)和递归法，奈何递归法让我摸不着头脑，因为个人是个"死脑筋"，所以在不断的短点调试下基本理清了原理，神奇的延伸到了递归和执行上下文(调用栈)的关系。

题源：leetcode-206

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

  1. 迭代法

    /**
 * 迭代法
 * @param {Node} head
 * @returns {Node}
 */
var reverseList = function(head) {
  let prev = null;
  let current = head;
  while(current) {
    const next = current.next; //保存下一个结点
    current.next = prev;
    prev = current; // 移动prev
    current = next; // 移动current
  }
  return prev;
}
reverseList(head);

  2. 递归法

    先不贴代码，免得重复。

对于递归法，我真的无从下手，因为本来递归就已经让人觉得混乱了🤪，况且还是加了链表这种数据结构，对此，我立马打断点！然后从网上找了不少资料将其理清了！不过，我们先来讲一下执行上下文吧！

执行上下文

每个函数调用都有自己的上下文。

执行上下文 是一个内部数据结构，每一个上下文都有一个关联的变量对象，它包含有关函数执行时的详细细节：

  • variable object 变量对象(对于全局执行上下文)；activation object 活动对象(对于函数执行上下文，活动对象当作变量对象)

    • variable object 包含：

      • 全局对象(在全局执行上下文) - the place where global vars (like window, document or console in a browser) reside

    • activation object 包含：

      • arguments

      • 函数内定义的变量

  • scope chain 作用域链(相当于链表)

    • 上下文中的代码在执行的时候，会创建变量对象的一个作用域链(scope chain)。这个作用域链决定了各级上下文中的代码在访问变量和函数时的顺序。代码正在执行的上下文的变量对象始终位于作用域链的最前端，全局执行上下文变量对象始终是最后端一个。

    • 在定义函数时，就会为它创建作用域链，预装载(父作用域)全局变量对象，并保存在内部的[[Scope]]中。

  • this的值(在这不讨论)

上述大部分其实是ES3所定义的(现在我明白为啥那么乱了。。这更新太快了，即便是规范。。)

分类：

  • 全局执行上下文

    • 全局上下文是最外层的上下文。根据 ECMAScript 实现的宿主环境，表示全局上下文的对象可能不一 样。在浏览器中，全局上下文就是我们常说的 window对象。它会执行两件事：创建一个全局的 window 对象（浏览器的情况下），并且设置 this 的值等于这个全局对象。一个程序中只会有一个全局执行上下文。

  • 函数执行上下文

    • 每当一个函数被调用时, 都会为该函数创建一个新的上下文。每个函数都有它自己的执行上下文，不过是在函数被调用时创建的。函数上下文可以有任意多个。

  • eval函数执行上下文(不讨论...)

生命周期：

  • 创建阶段(函数调用时)

    • 通过复制函数的[[Scope]]来创建其作用域链。

    • 确定this 的值

  • 执行阶段(函数执行中)

    • JS 代码开始逐条执行，在这个阶段，JS 引擎开始对定义的变量赋值、开始顺着作用域链访问变量、如果内部有函数调用就创建一个新的执行上下文压入执行栈并把控制权交出...

  • 销毁阶段

    • 一般来讲当函数执行完成后(return)，当前执行上下文（局部环境）会被弹出执行上下文栈并且销毁，控制权被重新交给执行栈上一层的执行上下文。(全局上下文在应用程序退出前才会被销毁，比如关闭网页或退出浏览器)。

    • 闭包另说。

执行上下文栈

当代码执行流进入函数时，函数的上下文被推到一个上下文栈上。 在函数执行完之后，上下文栈会弹出该函数上下文，将控制权返还给之前的执行上下文。ECMAScript 程序的执行流就是通过这个上下文栈进行控制的。

而对于嵌套执行(即递归)：

  • 当前函数被暂停；

  • 与它关联的执行上下文被一个叫做 执行上下文栈 的特殊数据结构保存；

  • 执行嵌套调用；

  • 嵌套调用结束后，从堆栈中恢复之前的执行上下文，并从停止的位置恢复外部函数。

剪不断，理还乱。

我们停一下，来点代码将它们捋一下好吗？

function compare(value1, value2) {
    if(value1 > value2){
    return true;
  }else if(value1 < value2){
    return false;
  }else {
        return -1;
  }
}
let result = compare(1,2);

我们直接看图：

context-example.png

图源：JavaScript高级程序设计

“反转”

了解了上面的内容后(主要是执行上下文栈)，我们可以开始使用这些性质反转链表了！递归解法代码：

/**
 * 递归法
 * @param {Node} head 
 * @returns {Node}
 */
var reverseLinkedList = function(head) {
  if(head === null || head.next === null) {
    return head;
  }
  let rset = reverseList(head.next);  // reset作为递归后的最后一个节点，也是反转后的第一个节点
  head.next.next = head;
  head.next = null;
  return rset; // rset的值一直不变为最后一个节点
}
reverseLinkedList(head);

为此我特地画了图(图示用3个结点的链表以方便理解)：

  1. 在全局上下文调用reverseList()

    step1.png

  2. 第一次嵌套调用

    step2.png

  3. 第二次嵌套调用

    step3.png

此时head.next = null了。而且我们可以看到其实图的左边head的指向原理就是函数调用有各自的执行上下文，其活动对象中保存的变量都是当时的值。

  1. 判断条件成立，return，弹栈。

    step4.png

  2. 回到之前的函数(执行上下文)继续执行后面的代码，注意看head的指向，就是第二个步骤的上下文！

    step5.png

  3. return rset 弹栈

    step6.png

  4. 回到之前的函数(执行上下文)继续执行后面的代码

    step7.png

  5. return rset 弹栈，栈空，反转完成。

    step8.png

Reference参考：