本文首发于 语雀文档

题目

https://leetcode-cn.com/problems/reverse-linked-list/

流程图、调试代码

https://github.com/blueju/leetcode/

第 1 次尝试

完全写不出来，没有思路。

但也不难，无非就是调换顺序，存储好上一个节点，修改当前节点的 next 为上一节点，但就纠结的一点是，第一个节点，它的上一个节点是多少？

但没有想到，第一个节点它根本不需要跳过，第一个节点最后它肯定是变成最后一个节点，那势必它的 next 肯定就是 null 啦。

这就一下好理解了。

第 2 次尝试（通过测试用例）

流程图

image.png

代码

  1. /**
  2.  * Definition for singly-linked list.
  3.  * function ListNode(val, next) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.next = (next===undefined ? null : next)
  6.  * }
  7.  */
  8. /**
  9.  * @param {ListNode} head
  10.  * @return {ListNode}
  11.  */
  12. var reverseList = function (head) {
  13.     let prev = null
  14.     let curr = head
  15.     while (curr) {
  16.         const next = curr.next
  17.         curr.next = prev
  18.         prev = curr
  19.         curr = next
  20.     }
  21.     return prev
  22. };

总结

要记得先暂存 curr 当前节点的 next 下一个，不然链表关系就断了。

第 3 次尝试

题目说除了迭代，还可以使用递归。 为了进一步弄清楚，迭代和递归的区别于转换，我觉得继续尝试一下。

好吧，试了下，写不出来，总觉的差在哪了

总结

看了题解发现，主要把握三点：

  1. 如何 return

    因为我们需要 return 的头节点是最后的节点，那只有一种办法，那就是一层层 return 递归函数中 return 中的值，这样才能把最底层嵌套里的最后节点拿出来

  2. 如何修改指向

    通过以上一点，我们可以知道，递归函数的 return，是需要一直 return 到最外层的，所以期间不得对其做修改的。 平时我们一般用到 xxx.next 就完了，但这里就需要用到 next.next，这也是我没想到的

第 4 次尝试（通过测试用例）

代码

  1. /**
  2.  * Definition for singly-linked list.
  3.  * function ListNode(val, next) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.next = (next===undefined ? null : next)
  6.  * }
  7.  */
  8. /**
  9.  * @param {ListNode} head
  10.  * @return {ListNode}
  11.  */
  12. var reverseList = function (head) {
  13.     if (head === null || head.next === null) {
  14.         return head
  15.     }
  16.     const result = reverseList(head.next)
  18.     head.next.next = head
  19.     head.next = null
  21.     return result
  22. };

总结

什么是递归，就是最里面的先执行。
先举例从里层算，一层层往后推，找到重复部分，然后封起来，考虑边界情况（比如：输入的 head 就是 null）。
image.png
反转链表.pptx