【2022-09-23每日一题】707. 设计链表[Medium]
2022-09-23
3分钟阅读时长
2022-09-23每日一题：707. 设计链表
难度：Medium
标签：设计 、 链表
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：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个节点。
示例：
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
提示：
- 所有
val值都在[1, 1000]之内。 - 操作次数将在
[1, 1000]之内。 - 请不要使用内置的 LinkedList 库。
方法一：单向链表
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
type MyLinkedList struct {
head *ListNode
count int
}
func Constructor() MyLinkedList {
return MyLinkedList{&ListNode{}, 0}
}
func (this *MyLinkedList) Get(index int) int {
// 获取链表中第 index 个节点的值。如果索引无效，则返回-1。
if index < 0 || index >= this.count {
return -1
}
pred := this.head
for i := 0; i <= index; i++ {
pred = pred.Next
}
return pred.Val
}
func (this *MyLinkedList) AddAtHead(val int) {
this.AddAtIndex(0, val)
}
func (this *MyLinkedList) AddAtTail(val int) {
this.AddAtIndex(this.count, val)
}
// 在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
func (this *MyLinkedList) AddAtIndex(index int, val int) {
if index > this.count {
return
}
if index < 0 {
index = 0
}
this.count++
pred := this.head
for i := 0; i < index; i++ {
pred = pred.Next
}
toAdd := &ListNode{val, pred.Next}
pred.Next = toAdd
}
// 如果索引 index 有效，则删除链表中的第 index 个节点
func (this *MyLinkedList) DeleteAtIndex(index int) {
if index < 0 || index >= this.count {
return
}
this.count--
pred := this.head
for i := 0; i < index; i++ {
pred = pred.Next
}
pred.Next = pred.Next.Next
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Get(index);
* obj.AddAtHead(val);
* obj.AddAtTail(val);
* obj.AddAtIndex(index,val);
* obj.DeleteAtIndex(index);
*/
复杂度分析
时间复杂度：初始化消耗 O(1)，get 消耗 O(index)，addAtHead 消耗 O(1)，addAtTail 消耗 O(n)，其中 n 为链表当前长度，即 addAtHead，addAtTail 和 addAtIndex 已调用次数之和，addAtIndex 消耗 O(index)。
空间复杂度：所有函数的单次调用空间复杂度均为 O(1)，总体空间复杂度为 O(n)，其中 n 为 addAtHead，addAtTail 和 addAtIndex 调用次数之和。
方法二：双向链表
type node struct {
val int
prev, next *node
}
type MyLinkedList struct {
head, tail *node
count int
}
func Constructor() MyLinkedList {
head, tail := &node{}, &node{}
head.next = tail
tail.prev = head
return MyLinkedList{head, tail, 0}
}
func (this *MyLinkedList) Get(index int) int {
if index < 0 || index >= this.count {
return -1
}
var cur *node
if index+1 < this.count-index {
cur = this.head
for i := 0; i <= index; i++ {
cur = cur.next
}
} else {
cur = this.tail
for i := 0; i < this.count-index; i++ {
cur = cur.prev
}
}
return cur.val
}
func (this *MyLinkedList) AddAtHead(val int) {
this.AddAtIndex(0, val)
}
func (this *MyLinkedList) AddAtTail(val int) {
this.AddAtIndex(this.count, val)
}
func (this *MyLinkedList) AddAtIndex(index int, val int) {
if index > this.count {
return
}
if index < 0 {
index = 0
}
var pred, cur *node
if index+1 < this.count-index {
cur = this.head
for i := 0; i <= index; i++ {
cur = cur.next
}
pred = cur.prev
} else {
cur = this.tail
for i := 0; i < this.count-index; i++ {
cur = cur.prev
}
pred = cur.prev
}
this.count++ // 放后面
toAdd := &node{val, pred, cur}
cur.prev = toAdd
pred.next = toAdd
}
func (this *MyLinkedList) DeleteAtIndex(index int) {
if index < 0 || index >= this.count {
return
}
var pred, cur *node
if index+1 < this.count-index {
cur = this.head
for i := 0; i <= index; i++ {
cur = cur.next
}
pred = cur.prev
} else {
cur = this.tail
for i := 0; i < this.count-index; i++ {
cur = cur.prev
}
pred = cur.prev
}
this.count-- // 放后面
pred.next = cur.next
cur.next.prev = pred
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Get(index);
* obj.AddAtHead(val);
* obj.AddAtTail(val);
* obj.AddAtIndex(index,val);
* obj.DeleteAtIndex(index);
*/
复杂度分析
时间复杂度：初始化消耗 O(1)，get 消耗 O(index)，addAtHead 消耗 O(1)，addAtTail 消耗 O(n)，其中 n 为链表当前长度，即 addAtHead，addAtTail 和 addAtIndex 已调用次数之和，addAtIndex 消耗 O(index)。
空间复杂度：所有函数的单次调用空间复杂度均为 O(1)，总体空间复杂度为 O(n)，其中 n 为 addAtHead，addAtTail 和 addAtIndex 调用次数之和。