707. 设计链表
题目
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：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:
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 Node struct {
Val int
Next *Node
}
type MyLinkedList struct {
VirtualHead *Node // 虚拟头节点
}
func Constructor() MyLinkedList {
node := &Node{}
node.Next = nil
return MyLinkedList{VirtualHead: node}
}
// 获取链表中第 index 个节点的值。如果索引无效，则返回-1。
func (this *MyLinkedList) Get(index int) int {
count := 0
ret := -1
cur_node := this.VirtualHead.Next
for index >= 0 && cur_node != nil {
if index == count {
ret = cur_node.Val
break
}
count++
cur_node = cur_node.Next
}
return ret
}
// 在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
func (this *MyLinkedList) AddAtHead(val int) {
cur_head := this.VirtualHead.Next
// 真实头结点为空
if cur_head == nil {
this.VirtualHead.Next = &Node{Val: val}
} else {
// 真实头结点非空
insertNode := &Node{Val: val}
insertNode.Next = cur_head
this.VirtualHead.Next = insertNode
}
return
}
// 将值为 val 的节点追加到链表的最后一个元素。
func (this *MyLinkedList) AddAtTail(val int) {
cur_node := this.VirtualHead.Next
pre_node := this.VirtualHead
for cur_node != nil {
pre_node = cur_node
cur_node = cur_node.Next
}
pre_node.Next = &Node{Val: val}
}
// 在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
func (this *MyLinkedList) AddAtIndex(index int, val int) {
if index < 0 {
this.AddAtHead(val)
return
}
count := 0
cur_node := this.VirtualHead.Next
pre_node := this.VirtualHead
for index >= 0 && cur_node != nil {
if index == count {
insertNode := &Node{Val: val}
insertNode.Next = cur_node
pre_node.Next = insertNode
}
count++
pre_node = cur_node
cur_node = cur_node.Next
}
if index == count {
this.AddAtTail(val)
}
}
// 如果索引 index 有效，则删除链表中的第 index 个节点。
func (this *MyLinkedList) DeleteAtIndex(index int) {
count := 0
cur_node := this.VirtualHead.Next
pre_node := this.VirtualHead
for index >= 0 && cur_node != nil {
if index == count {
pre_node.Next = cur_node.Next
break
}
count++
pre_node = cur_node
cur_node = cur_node.Next
}
return
}