乐趣区

关于javascript:翻转单链表

反转单链表

明天跟大家分享一个曾经被写烂了的题目 –> 反转单链表

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

然而!每次感觉本人记的很好了,一到写代码的时候还是两眼一抹黑。

这就是知其然不知其所以然的结果,肯定要深刻的弄懂一个题目,并不要只记住代码,世上代码千千万,又能记住多少呢?

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

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

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

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

明天的分享咱们到这里也就完结了,心愿能够让你有所播种,Bye~

退出移动版