回到课程

反向输出单链表

重要程度: 5

反向输出前一个任务 输出一个单链表 中的单链表。

使用两种解法:循环和递归。

使用递归

递归逻辑稍微有点儿棘手。

我们需要先输出列表的其它元素,然后输出当前的元素:

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);

请注意,递归解法实际上也是这样做的:它顺着链表,记录每一个嵌套调用里链表上的元素(在执行上下文堆栈里),然后输出它们。