【数据结构与算法】(7):反转单向链表


字数:522 阅读时长:2分钟 阅读:85

链表是一种 动态且零散 的数据结构,它由一系列节点组成,每个节点包含数据和指向下一个节点的指针。本文介绍一下如何将数组变成链表,并且实现 反转单向链表 的算法。

数据结构与算法 · 反转单向链表

一、链表 VS 数组

  • 链表特点

数据结构与算法 · 链表

  • 链表 VS 数组

数据结构与算法 · 链表 VS 数组

二、数组转单向链表

  • TS 代码演示
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
interface ILinkListNode {
value: number
next?: ILinkListNode
}

type ItemNode = ILinkListNode | undefined

function createLinkList(arr: number[]): ILinkListNode {
const len = arr.length;
if (len === 0) throw new Error('arr is empty');

let currNode: ILinkListNode = {
value: arr[len - 1]
}

if (len===1) return currNode

for (let i = len-2; i >= 0; i--) {
currNode = {
value: arr[i],
next: currNode
}
}

return currNode
}

三、反转单向链表

  1. 反转单向链表思路图示

数据结构与算法 · 反转单向链表

  1. TS 代码演示
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
function reverseLinkList(listNode: ILinkListNode): ILinkListNode {
let prevNode: ItemNode = undefined
let currNode: ItemNode = undefined
let nextNode: ItemNode = listNode

while (nextNode) {
// 第一个元素删掉 next ,防止循环引用
if (currNode && !prevNode) {
delete currNode.next
}

// 反转指针
if (currNode && prevNode) {
// @ts-ignore
currNode.next = prevNode
}

// 指针整体向后移
prevNode = currNode
currNode = nextNode
nextNode = nextNode?.next

}

// 最后一个补充:当 nextNode 为空时,此时 currNode 尚未设置 next 指向
currNode!.next = prevNode

return currNode!
}

四、测试

1
2
3
4
5
6
7
const arr = [100, 200, 300, 400, 500]
const res = createLinkList(arr)
console.log(res)
let str1 = JSON.stringify(res)
let link1 = JSON.parse(str1)
let list1 = reverseLinkList(link1)
console.log(list1)

数组转链表输出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
{
"value": 100,
"next": {
"value": 200,
"next": {
"value": 300,
"next": {
"value": 400,
"next": {
"value": 500
}
}
}
}
}

反转链表输出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
{
"value": 500,
"next": {
"value": 400,
"next": {
"value": 300,
"next": {
"value": 200,
"next": {
"value": 100
}
}
}
}
}

《数据结构与算法》系列

  1. 什么是算法复杂度
  2. 堆(heap)、栈(stack)、队列(queue)
  3. 把一个数组旋转k步
  4. 判断字符串是否括号匹配
  5. 数组、栈、链表、队列结构与对比
  6. 用两个栈实现一个队列
  7. 反转单向链表
  8. 用链表实现队列
  9. 二分查找
  10. 查找两数之和

欢迎访问:天问博客

本文作者: Tiven
发布时间: 2023-07-15
最后更新: 2023-07-20
本文标题: 【数据结构与算法】(7):反转单向链表
本文链接: https://www.tiven.cn/p/fc060cbe/
版权声明: 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处!
欢迎留言,提问 ^_^
个人邮箱: tw.email@qq.com
notification icon
博客有更新,将会发送通知给您!