设计链表

学习文本来源：代码随想录

力扣地址

题意：

在链表类中实现这些功能：

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

示例：

输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]
解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2); // 链表变为 1->2->3
myLinkedList.get(1); // 返回 2
myLinkedList.deleteAtIndex(1); // 现在，链表变为 1->3
myLinkedList.get(1); // 返回 3

思路

这道题目设计链表的五个接口：

获取链表第index个节点的数值
在链表的最前面插入一个节点
在链表的最后面插入一个节点
在链表第index个节点前面插入一个节点
删除链表的第index个节点
可以说这五个接口，已经覆盖了链表的常见操作，是练习链表操作非常好的一道题目

链表操作的两种方式：

直接使用原来的链表来进行操作。
设置一个虚拟头结点在进行操作。

代码

golang:

type SingleNode struct{
    Val int
    Next *SingleNode
}

type MyLinkedList struct{
    dummyHead *SingleNode
    Size int
}

func Constructor() MyLinkedList {
    newNode := &SingleNode{
        -999,
        nil,
    }
    return MyLinkedList{
        dummyHead: newNode,
        Size: 0,
    }
}

func (this *MyLinkedList) Get(index int) int {
    if this == nil || index < 0 || index >= this.Size { // 如果索引无效则返回-1
        return -1
    }
    // 让cur等于真正头节点
    cur := this.dummyHead.Next   // 设置当前节点为真实头节点
    for i := 0; i < index; i++ { // 遍历到索引所在的节点
        cur = cur.Next
    }
    return cur.Val // 返回节点值
}

func (this *MyLinkedList) AddAtHead(val int) {
    this.dummyHead.Next =  &SingleNode{
        Val: val,
        Next:this.dummyHead.Next
    }             // 新节点变为头节点
    this.Size++   // 链表大小增加1
}

func (this *MyLinkedList) AddAtTail(val int) {
    newNode := &SingleNode{Val: val} // 创建新节点
    cur := this.dummyHead            // 设置当前节点为虚拟头节点
    for cur.Next != nil {            // 遍历到最后一个节点
        cur = cur.Next
    }
    cur.Next = newNode // 在尾部添加新节点
    this.Size++        // 链表大小增加1
}

func (this *MyLinkedList) AddAtIndex(index int, val int) {
    if index < 0 { // 如果索引小于0，设置为0
        index = 0
    } else if index > this.Size { // 如果索引大于链表长度，直接返回
        return
    }

    newNode := &SingleNode{Val: val} // 创建新节点
    cur := this.dummyHead            // 设置当前节点为虚拟头节点
    for i := 0; i < index; i++ {     // 遍历到指定索引的前一个节点
        cur = cur.Next
    }
    newNode.Next = cur.Next // 新节点指向原索引节点
    cur.Next = newNode      // 原索引的前一个节点指向新节点
    this.Size++             // 链表大小增加1
}

func (this *MyLinkedList) DeleteAtIndex(index int) {
    if index < 0 || index >= this.Size { // 如果索引无效则直接返回
        return
    }
    cur := this.dummyHead        // 设置当前节点为虚拟头节点
    for i := 0; i < index; i++ { // 遍历到要删除节点的前一个节点
        cur = cur.Next
    }
    if cur.Next != nil {
        cur.Next = cur.Next.Next // 当前节点直接指向下下个节点，即删除了下一个节点
    }
    this.Size-- // 注意删除节点后应将链表大小减一
}

链表-设计链表