输出一个单链表&&反向输出一个单链表（最后有原链接）

66 阅读 0 评论 44 点赞

我是靠谱客的博主虚拟悟空，最近开发中收集的这篇文章主要介绍输出一个单链表&&反向输出一个单链表（最后有原链接），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

输出一个单链表

假设我们有一个单链表：

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

编写一个可以逐个输出链表元素的函数 printList(list)。

使用两种方式实现：循环和递归。

哪个更好：用递归还是不用递归的？

基于循环的解法：

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

function printList(list) {
  let tmp = list;

  while (tmp) {
    alert(tmp.value);
    tmp = tmp.next;
  }

}

printList(list);

请注意，我们使用了一个临时变量 tmp 来遍历链表。从技术上讲，我们可以使用函数的入参 list 来代替：

function printList(list) {

  while(list) {
    alert(list.value);
    list = list.next;
  }

}

……但是这不够明智。未来我们可能想要扩展这个函数，使用这个链表做其他的事儿，如果我们修改了 list，那么我们就失去了这个能力。说到好的变量命名，list 在这里是链表本身。代表它的第一个元素。它应该保持原样，这是清晰可靠的。从另一个方面来说，tmp 是充当了完全遍历链表的角色，就像 for 循环中的 i 一样。

递归解法

printList(list) 的递归实现遵循一个简单的逻辑：为了输出链表，我们应该输出 list 的当前的元素，list.next 同理：

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

function printList(list) {

  alert(list.value); // 输出当前元素

  if (list.next) {
    printList(list.next); // 链表中其余部分同理
  }

}

printList(list);

哪个更好呢？

从技术上讲，循环更有效。这两种解法的做了同样的事儿，但循环不会为嵌套函数调用消耗资源。

另一方面，递归解法更简洁，有时更容易理解。

反向输出一个单链表

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

解决方案

使用递归

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

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

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

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

原链接：递归和堆栈