设计链表
LeetCode0707. 设计链表
题目描述
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:val
和 next
。val
是当前节点的值,next
是指向下一个节点的指针/引用。如果要使用双向链表,则还需要一个属性 prev
以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能:
- get(index):获取链表中
index
号节点的值。如果索引无效,则返回-1
。
- addAtHead(val):在链表的第一个元素之前添加一个值为
val
的节点。插入后,新节点将成为链表的第一个节点。
- addAtTail(val):将值为
val
的节点追加到链表的最后一个元素。
- addAtIndex(index,val):在链表中的
index
号节点之前添加值为 val
的节点。如果index
等于链表的长度,则该节点将附加到链表的末尾。如果 index
大于链表长度,则不会插入节点。如果index
小于0,则在头部插入节点。
- deleteAtIndex(index):如果索引
index
有效,则删除链表中的第 index
个节点。
示例:
1
2
3
4
5
6
7
|
MyLinkedList linkedList = new MyLinkedList();
linkedList.AddAtHead(1);
linkedList.AddAtTail(3);
linkedList.AddAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.Get(1); //返回2
linkedList.DeleteAtIndex(1); //现在链表是1-> 3
linkedList.Get(1); //返回3
|
思路
题目要求
- 创建一个链表类,类中有构造器和五个方法:
- 获取链表第index个节点的数值
- 在链表的最前面插入一个节点
- 在链表的最后面插入一个节点
- 在链表第index个节点前面插入一个节点
- 删除链表的第index个节点
本题可采用单链表和双链表两种方式
单链表是最简单的一种,它提供了在常数时间内的 addAtHead
操作和在线性时间内的 addAtTail
的操作。
双链表是最常用的一种,因为它提供了在常数时间内的 addAtHead
和 addAtTail
操作,并且优化了插入和删除。
双链表比单链表快得多,测试用例花费的时间比单链表快了两倍。但是它更加复杂,它包含了 size
,记录链表元素个数,不计伪头伪尾。
为了使插入和删除时间消耗更少,我使用双链表;为了简化插入和删除,我在头节点前加入一个伪头。
注意
-
Go 语言中没有类(Class)的概念,但可以使用结构体(Structs)对属性进行封装,结构体就像是类的一种简化形式
-
Go 方法是作用在接收者(Receiver)上的一个函数,接收者是某种类型的变量。因此方法是一种特殊类型的函数。
定义方法的格式如下:
1
|
func (recv receiver_type) methodName(parameter_list) (return_value_list) { ... }
|
-
Go语言中没有提供构造函数相关的特殊机制,用户根据自己的需求,将参数使用函数传递到结构体构造参数中即可完成构造函数的任务。
-
index
从0
开始
-
在添加节点后size++
,删除节点后size--
代码
Go
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
// MyLinkedList 双链表(类)
type MyLinkedList struct {
size int
dummyHead *Node
dummyTail *Node
}
// Node 节点(结构体)
type Node struct {
value int
pre *Node
next *Node
}
// Constructor 构造方法
func Constructor() MyLinkedList {
dummyHead := new(Node)
dummyTail := new(Node)
dummyHead.next = dummyTail
dummyTail.pre = dummyHead
return MyLinkedList{0, dummyHead, dummyTail}
}
// GetNode 获取链表index号节点
func (this *MyLinkedList) GetNode(index int) *Node {
p := this.dummyHead.next
if index <= (this.size >> 1) {
// 从前遍历
for i := 0; i < index; i++ {
p = p.next
}
} else {
// 从后遍历
p = this.dummyTail.pre
for i := 0; i < this.size-1-index; i++ {
p = p.pre
}
}
return p
}
// Get 获取链表index号节点的数值
func (this *MyLinkedList) Get(index int) int {
if index < 0 || index >= this.size {
// 索引无效
return -1
}
return this.GetNode(index).value
}
// AddAtHead 在链表的最前面插入一个节点
func (this *MyLinkedList) AddAtHead(val int) {
head := new(Node)
head.value = val
head.pre = this.dummyHead
head.next = this.dummyHead.next
this.dummyHead.next = head
head.next.pre = head
this.size++
}
// AddAtTail 在链表的最后面插入一个节点
func (this *MyLinkedList) AddAtTail(val int) {
tail := new(Node)
tail.value = val
tail.pre = this.dummyTail.pre
tail.next = this.dummyTail
this.dummyTail.pre = tail
tail.pre.next = tail
this.size++
}
// AddAtIndex 在链表index号节点前面插入一个节点
func (this *MyLinkedList) AddAtIndex(index int, val int) {
if index < 0 {
// 在链表的最前面插入一个节点
this.AddAtHead(val)
return
}
if index == this.size {
this.AddAtTail(val)
return
}
if index > this.size {
return
}
indexNode := this.GetNode(index)
newNode := new(Node)
newNode.value = val
newNode.pre = indexNode.pre
newNode.next = indexNode
indexNode.pre = newNode
newNode.pre.next = newNode
this.size++
}
func (this *MyLinkedList) DeleteAtIndex(index int) {
if index < 0 || index >= this.size {
// 索引无效
return
}
indexNode := this.GetNode(index)
indexNode.pre.next = indexNode.next
indexNode.next.pre = indexNode.pre
this.size--
}
|
Link
GitHub