盒子
盒子
文章目录
  1. 题目
  2. 暴力解题
  3. 递归

反转单链表

题目

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

示例:

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

暴力解题

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* 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%,看着数就知道不怎么样了,用别的方法解题。

递归

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

1
2
3
4
5
// cur表示当前节点
let temp = cur.next
cur.next = pre
pre = cur
cur = temp

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 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)。

欢迎关注公众号
扫码关注我的微信公众号-大前端合集
  • 微信公众号-大前端合集