反转单链表

今天跟大家分享一个已经被写烂了的题目 --> 反转单链表

相信大家一定在日常的工作、面试中被这道题所难倒过，而且也相信很多人都会在网上查找实现方案，并且会牢牢记住。

但是！每次觉得自己记的很好了，一到写代码的时候还是两眼一抹黑。

这就是知其然不知其所以然的后果，一定要深入的弄懂一个题目，并不要只记住代码，世上代码千千万，又能记住多少呢？

接下来，我们就来看下如何实现一个单链表的反转。

1. 创建一个单链表

首先我们需要一个单链表。（相信单链表的定义一定不需要多说，大家都知道）

上栗子：🌰

const linkList = {
  val: 1,
  next: {
    val: 2,
    next: {
      val: 3,
      next: {
        val: 4,
        next: {
          val: 5,
          next: {
            val: 6,
            next: null
          }
        }
      }
    }
  }
}

首先映入眼帘的是一长串嵌套的数据，嗯，乍一看有点儿眼花。

请原谅作者的偷懒，但是这也是最容易让人理解的方式。

2. 单链表反转

数据定义好之后，我们就需要来将此链表做反转。

看好了，接下来的代码正是让大家疑惑的点。

🌰：

function reverseLinkList (linkList) {
  if (!linkList) return null

  let result = null
  let preLinkList = linkList
  let nextLinkList = linkList.next

  while(preLinkList) {
    preLinkList.next = result
    result = preLinkList
    preLinkList = nextLinkList

    if(nextLinkList) {
      nextLinkList = nextLinkList.next
    }
  }
  return result
}

仔细一看，司高义！满屏惊叹。

然后~~~，这是写了个什么玩意儿，看不懂。

莫慌，这都是大家疑惑的点，我们来详细解释一下。

题目解析：

1. 变量解析

let result = null
let preLinkList = linkList
let nextLinkList = linkList.next

这里定义了三个变量

• result 是获取到的反转后的结果
• preLinkList是当前操作的链表
• nextLinkList 保存的是需要遍历的链表

2. 循环解析

while(preLinkList) {
  preLinkList.next = result
  result = preLinkList
  preLinkList = nextLinkList

  if(nextLinkList) {
    nextLinkList = nextLinkList.next
  }
}

这个循环也是大家最疑惑的地方。给大家详细说明一下。接下来我们看下执行步骤。

• 每次执行都先将 preLinkList 变形为我们想要的数据。它的变化规则如下。
• 之后将此数据赋值在 result 上。
• 然后 preLinkList 递进，递进的条件就是将 nextLinkList 赋值给 preLinkList

接下来我们看下整体的执行流程图解。

图解.png

以上就是反转单链表的全部流程了。

今天的分享我们到这里也就结束了，希望可以让你有所收获，Bye~