206 - 反转链表(reverse-linked-list)

Create by jsliang on 2019-7-13 07:54:49
Recently revised in 2019-7-13 08:42:07

一 目录

不折腾的前端,和咸鱼有什么区别

目录
一 目录
二 前言
三 解题
四 执行测试
五 LeetCode Submit
六 解题思路
七 进一步思考

二 前言

返回目录

反转一个单链表。

示例:

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

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?

三 解题

返回目录

小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 的解题思路。

  • 解题代码
var reverseList = (head, q = null) => {
  if (head) {
    return reverseList(head.next, {
      val: head.val,
      next: q,
    });
  }
  return q;
}

四 执行测试

返回目录

  • head
let head = {
  val: 1, next: {
    val: 2, next: {
      val: 3, next: {
        val: 4, next: {
          val: 5, next: null,
        },
      },
    },
  },
};
  • return
{
  val: 5, next: {
    val: 4, next: {
      val: 3, next: {
        val: 2, next: {
          val: 1, next: null,
        },
      },
    },
  },
}

五 LeetCode Submit

返回目录

√ Accepted
  √ 27/27 cases passed (80 ms)
  √ Your runtime beats 92.17 % of javascript submissions
  √ Your memory usage beats 6.29 % of javascript submissions (36.1 MB)

六 解题思路

返回目录

智商是硬伤,知识点也可能是

经过这次解题,jsliang 将链表给标记上了,等到系统学习算法与数据结构的时候,链表是必须搞懂的点之一。

首先,上面题解不是我写出来的,看的是评论区的题解,原代码是:

const reverseList = (head, q = null) => head !== null ? reverseList(head.next, { val: head.val, next: q }) : q;

传说中的一行题解。

然后,怕小伙伴们跟我一样懵逼,jsliang 进行了改编:

var reverseList = (head, q = null) => {
  console.log(q);
  if (head) {
    return reverseList(head.next, {
      val: head.val,
      next: q,
    });
  }
  return q;
}

最后,为了方便小伙伴们理解,jsliangq 的过程打印了出来:

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

嗯,对着 console.log() 来思考这次递归的用意,小伙伴们应该能清楚怎么反转链表了。(虽然下次还是可能写不出,但是没关系,后面大家一起系统学习~)

七 进一步思考

返回目录

上面使用了递归,下面看看迭代解法:

var reverseList = function(head) {
  if (head == null || head.next == null) {
    return head;
  }
  var current = head;
  var previous = null;
  while (current != null) {
    next = current.next;
    current.next = previous;
    previous = current;
    current = next;
  }
  return previous;
};

提交结果是:

√ Accepted
  √ 27/27 cases passed (80 ms)
  √ Your runtime beats 92.17 % of javascript submissions
  √ Your memory usage beats 70.6 % of javascript submissions (34.8 MB)

感兴趣的小伙伴可以推演下迭代的思路,在此 jsliang 就不多滴滴啦~


不折腾的前端,和咸鱼有什么区别!

图

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

知识共享许可协议
jsliang 的文档库梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。

Copyright © jsliang.top 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-07-13 09:41:10

results matching ""

    No results matching ""