遍历链表

链表是一个常用的、基础的数据结构，可以使用非线性内存地址存放线性的数据。

遍历链表主要有迭代法和递归法两种方式去遍历，其中后序遍历链表可以很好的反向读取（从尾到头）链表中的值。

下面的代码也可以理解为将链表转为数组。

Code

迭代法：

function iterativeTraverse(head) {
  const result = [];
  while (head !== null) {
    result.push(head.val);
    head = head.next;
  }
  return result;
}

递归法（正向）：

  const result = [];
  function helper(head) {
    if (head === null) return;
    result.push(head.val);
    helper(head.next);
  }
  helper(head);
  return result;

递归法（反向）：

function recursiveTraversePost(head) {
  const result = [];
  function helper(head) {
    if (head === null) return;
    helper(head.next);
    result.push(head.val);
  }
  helper(head);
  return result;
}

Test Cases

const {
  generateLinkedList,
  iterativeTraverse,
  recursiveTraverse,
  recursiveTraversePost,
} = require('./traverse');
describe('traverseLinkedList', () => {
  const head = generateLinkedList([0, 1, 2, 3, 4]);
  it('iterative', () => {
    const arr = iterativeTraverse(head);
    expect(arr).toEqual([0, 1, 2, 3, 4]);
  });
  it('recursive', () => {
    const arr = recursiveTraverse(head);
    expect(arr).toEqual([0, 1, 2, 3, 4]);
  });
  it('recursivePost', () => {
    const arr = recursiveTraversePost(head);
    expect(arr).toEqual([0, 1, 2, 3, 4].reverse());
  });
});