前端刷题路-Day3

链表反转（题号24）

题目

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL  
输出: 5->4->3->2->1->NULL

限制：

• 0 <= 节点个数 <= 5000

链接

leetcode-cn.com/problems/fa…

解释

关于链表其实自己的理解一直都错了，根据网上的教程来看，链表的本质貌似是一个数组，数组中有一个个元素，如下：

[{
 val: 1,
 next: 2,
}, {
 val: 2,
 next: 3,
}, {
 val: 3,
 next: null
}]

但其实并不是，链表的本质有点类似于树的形态，它是这样的：

{
  "val": 1,
  "next": {
    "val": 2,
    "next": {
      "val": 3,
      "next": {
        "val": 4,
        "next": {
          "val": 5,
          "next": null
        }
      }
    }
  }
}

每个next都包含着剩下所有的内容，比方说这是一个5组数据的链表，那么第一个元素的next包含着剩下四组的数据的所有内容，第二个元素的next包含着剩下三组元素的所有内容，这才是链表。

自己的解法

var newReverseList = function(head) {
  var newList = {}
  var arr = []
  if (!head) return null
  function getNode(list) {
    if (list !== null) {
      arr.push(list.val)
      getNode(list.next)
    }    
  }
  getNode(head)
  function addNode(index) {
    if (index >= 0) {
      return {
        val: arr[index],
        next: addNode(index - 1)
      }
    } else {
      return null
    }
  }
  newList = addNode(arr.length - 1)
  return newList
};

看看这个答案，明显就是菜鸡写的，首选定义一个方法来获取链表中所有的val，拿到数组后再递归写入新的链表，暨此实现反转链表的效果。

但这样做时间复杂度有O(2n)，这么高，这还是经过一些简化的代码，否则后续写入的时候又是持续的低柜，时间复杂度会更高，不过对于初学者来说这样的代码看起来十分正常。

更好的答案

var newReverseList = function(head) {
  if (!head || !head.next) return null
  var cur = head;
  var pre = null;
  while (cur) {
    var next = cur.next;
    cur.next = pre;
    pre = cur;
    cur = next
  }
  return pre
};

这个答案一度让我无法理解，因为链表的特殊结构，这样的操作根本就看不懂了，几次尝试打印才勉强理解了。

首先，代码的if判断就不解释了，为了排除某些特殊情况，下面才是重点。

首先声明了两个变量，cur为当前的链表，pre为反转后的链表。

之后while循环cur变量，在循环内部，首先拿出cur的next，之后将cur的next属性赋值为pre。之后将pre赋值为改变next后的pre，最后，将cur赋值为其next属性。

之后开始循环，一层层展开cur，pre也是一层层的增加赋值，pre是从里到外增加，而cur是从外到里减少，这也正契合了链表反转的主题。