以逆序输出单链表 - JavaScript 中文教程

以逆序输出上一个任务输出单链表中的单链表。

给出两种解决方案：使用循环和使用递归。

使用递归

这里的递归逻辑有点棘手。

我们需要先输出链表的剩余部分，然后输出当前部分。

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

function printReverseList(list) {

  if (list.next) {
    printReverseList(list.next);
  }

  alert(list.value);
}

printReverseList(list);

使用循环

循环版本也比直接输出稍微复杂一些。

我们无法获取 list 中的最后一个值。我们也不能“回溯”。

所以我们可以先按顺序遍历所有项目，并将它们存储在一个数组中，然后以逆序输出我们存储的内容。

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

function printReverseList(list) {
  let arr = [];
  let tmp = list;

  while (tmp) {
    arr.push(tmp.value);
    tmp = tmp.next;
  }

  for (let i = arr.length - 1; i >= 0; i--) {
    alert( arr[i] );
  }
}

printReverseList(list);

请注意，递归解决方案实际上做了完全相同的事情：它遍历链表，将项目存储在嵌套调用链中（在执行上下文栈中），然后输出它们。