反转单链表

不作声

发布于 2021-01-06 18:40:14

3760

发布于 2021-01-06 18:40:14

文章被收录于专栏：M不作声M不作声

题目

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

示例：

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

暴力解题

先使用别的数据结构存储所有的元素，然后再遍历该数据类型一次，为新链表添加节点。

使用栈非常好解决，将所有的节点依次入栈，然后依次出栈，生成一个节点。

由于栈的特性，先进后出后，所有的元素会自然被倒序。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
 let stack = []
  let h = head
  while(h) {
    stack.push(h)
    // 经过处理，每个节点的next都指向空，即将整个链表拆成单个的节点
    temp = h.next
    h.next = null
    h = temp
  }
  let node = stack.pop()
  let dummy = node
  while(stack.length !== 0) {
    let temp = stack.pop()
    node.next = temp
    node = node.next
  }
  
  return dummy
};

提交以后给了结果：

暴力解

这结果简直拉胯，我们来做时间和空间复杂度分析，将链表遍历一遍拆掉入栈，然后再将栈遍历一遍出栈生成链表，时间复杂度大致为O(2n)，而为了存储节点借用了一个栈的数据结构空间复杂度为O(n)，中间临时变量忽略不计，生成一个新的链表又使用了，空间复杂度为O(2n)。

时间复杂度和空间复杂度都为O(2n)，运行时间打败48%，内存消耗打败60%，看着数就知道不怎么样了，用别的方法解题。

递归

反转链表根据分治法的思想分解问题后，即将整个链表分解成小问题，问题就变成了反转两个节点，我们只需做以下操作：

// cur表示当前节点
let temp = cur.next
cur.next = pre
pre = cur
cur = temp

当每两个节点之间的指向都改变后，整个链表的反转也完成了，代码如下：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
 let dummy = null, cur = head, temp
 while(cur) {
    // 保存后边的链表
    temp = cur.next
    // 改变指向
    cur.next = dummy
    // 指针后移
    dummy = cur
    cur = temp
  }
  return dummy
};

通过这种方式只需要遍历一遍链表，而且只用了临时变量，时间复杂度为O(n)，空间复杂度为O(1)。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-12-27，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构

编程算法

本文分享自大前端合集微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

数据结构

编程算法

登录后参与评论

0 条评论

热度