leetcode：反转链表

描述：

题解：

思路一：使用迭代

使用迭代的思路跟之前所有链表的解法大同小异，主要是通过画图的方式来理清节点之间的关系。遍历整个链表，将当前节点的 next 指向它的 prev 即可。

ES6

function reverseList(linkedList) {
  //定义三个指针：前一个节点，当前节点，下一个节点
  let prev = null
  let curr = linkedList
  let nextTemp
  while (curr != null) {
    //存储下一个节点
    nextTemp = curr.next
    //把当前节点的next设置为prev
    curr.next = prev
    //当前节点变成上一个节点
    prev = curr
    //下一个节点变成当前节点
    curr = nextTemp
  }
  return prev
}

时间复杂度：O(n)

思路二：使用递归

递归的解法自己想半天没有想明白，官方的题解看了很久才看懂。主要感觉平时算法基本都是用迭代比较多，递归的思想并没有理解很透彻，练得也比较少。在网上找了一篇文章：为什么你学不会递归？告别递归，谈谈我的一些经验，里面刚好举了一个反转链表的例子，讲得比较通俗易懂。

ES6

function reverseList(head) {
  if (head == null || head.next == null) return head
  const p = reverseList(head.next)
  head.next.next = head
  head.next = null
  return p
}

时间复杂度：O(n)