链表算法（1）

对 Go 链表相关算法继续学习，并做了笔记。相关链接：代码随想录

203.移除链表元素

203. 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]
提示：

列表中的节点数目在范围 [0, 104] 内

1 <= Node.val <= 50

0 <= val <= 50

使用原链表（力扣超时）

这里以链表 1 4 2 4 来举例，移除元素4。

如果首元节点的值就是要移除的值，例如 head = [7,7,7,7,6], val = 7

直接移除首元节点

for head != nil && head.Val == val {

head = head.Next

}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
    // 先删除含 val 的首元节点，可能有多个所以循环
    for head != nil && head.Val == val{// head.Next != nil 不用考虑，因为最后一个节点就是指向nil的
            // head 指向下一个节点，相当于删除了原来的首元节点
            head = head.Next
    }

    // struct(节点)是值类型，传递的是副本
    cur := head
    for cur != nil && cur.Next != nil {
        if cur.Next.Val == val {
            cur.Next = head.Next.Next
        } else {
            cur = cur.Next
        }
    }
    return head
}

虚拟头结点

第一种方法中，移除首元节点和移除之后节点的方法不同。

如果添加一个虚拟头结点，那么对节点的移除操作就一致了。

最后 return dummyHead.Next

func removeElements(head *ListNode, val int) *ListNode {
    dummyHead := &ListNode{}
    dummyHead.Next = head

    cur := dummyHead
    for cur != nil && cur.Next != nil {
        if cur.Next.Val == val {
            cur.Next = cur.Next.Next
        } else {
            cur = cur.Next
        }
    }
    return dummyHead.Next
}

递归（未完成）

java思路

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(n)
 * @param head
 * @param val
 * @return
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return head;
        }

        // 假设 removeElements() 返回后面完整的已经去掉val节点的子链表
        // 在当前递归层用当前节点接住后面的子链表
        // 随后判断当前层的node是否需要被删除，如果是，就返回
        // 也可以先判断是否需要删除当前node，但是这样条件语句会比较不好想
        head.next = removeElements(head.next, val);
        if (head.val == val) {
            return head.next;
        }
        return head;

        // 实际上就是还原一个从尾部开始重新构建链表的过程
    }
}

707.设计链表

707. 设计链表

中等

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

MyLinkedList() 初始化 MyLinkedList 对象。

int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。

void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。

void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。

void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。

void deleteAtIndex(int 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
提示：

0 <= index, val <= 1000

请不要使用内置的 LinkedList 库。

调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。

单链表优化

链表设计及其初始化。链表中有链表大小 Size。在实现链表操作方法的时候，不要忘记 l.Size++ 和 l.Size-- 。

type SingleNode struct {
    Val int
    Next *SingleNode
}

type MyLinkedList struct {
    DummyHead *SingleNode
    Size int
}

func Constructor() MyLinkedList {
    NewDummyHead := &SingleNode {
        Val: -1,
        Next: nil,
    }

    return MyLinkedList{
        DummyHead: NewDummyHead,
        Size: 0,
    }
}

具体对链表的操作均使用虚拟头结点的方法，具体思路看下面。

一开始只觉得删除节点可以用这个思想，其他方法的思路都是梦到哪写哪，写的很糟糕。

针对自己写的版本的一些优化：

遍历链表优化：

只遍历到 index 即可。这时 cur 到达 index 的前一个节点。

如果不确定范围对不对，可以代入极端情况，例如 index = 0 的情况。具体看第三点。
```
        for i := 0; i < index; i++ {
            cur = cur.Next
        }
```

对 index 是否合法的判断也进行了优化。

之前自己写的时候，总想把 插入到 index 前 和插入到末尾的情况单独讨论，分别调用 AddAtHead() 和 AddAtTail 。但实际上可以整合到一起处理。

func (l *MyLinkedList) AddAtIndex(index int, val int)  {
    if index < 0 {
        index = 0
    } else if index > l.Size {// 题中 index == l.Size 会将该节点添加到链表末尾，所以是 l.Size 不是 l.Size -
        return
    }
    newNode := &SingleNode{Val: val}
    cur := l.DummyHead
    // cur 指向 index 的前一个节点
    for i := 0; i < index; i++ {
        cur = cur.Next
    }
    newNode.Next = cur.Next
    cur.Next = newNode
    l.Size++
}

统一使用虚拟头结点的思想，规范了变量名。如上面的代码所示。

统一遍历到 cur 指向 index 的前一个节点，然后通过 cur 进行操作。

例如下图的 AddAtIndex() 操作

这时 cur 已经指向了 index 的前一个节点，接下来只要添加节点就好了。

添加节点时， newNode 先指向 indexNode ，cur 再指向 newNode 。如果搞反了，后面的节点就丢失了。

如果不知道这么遍历对不对，可以代入极端情况，例如 index = 0 的情况。

index == 0，不进入循环。cur = DemmyHead

完整代码：

type SingleNode struct {
    Val int
    Next *SingleNode
}

type MyLinkedList struct {
    DummyHead *SingleNode
    Size int
}


func Constructor() MyLinkedList {
    NewDummyHead := &SingleNode {
        Val: -1,
        Next: nil,
    }

    return MyLinkedList{
        DummyHead: NewDummyHead,
        Size: 0,
    }
}


func (l *MyLinkedList) Get(index int) int {
    if l.Size < 1 {
        return -1
    }
    if l == nil || index > l.Size - 1 || index < 0 {// 加上了 l == nil 的判断
        return -1
    } else {
        cur := l.DummyHead.Next
        for i := 0; i < index; i++ {
            cur = cur.Next
        }
        return cur.Val
    }
    return -1
}


func (l *MyLinkedList) AddAtHead(val int)  {
    newNode := &SingleNode{Val: val}
    newNode.Next = l.DummyHead.Next
    l.DummyHead.Next = newNode
    l.Size++
}


func (l *MyLinkedList) AddAtTail(val int)  {
    newNode := &SingleNode{Val: val}
    cur := l.DummyHead
    for cur.Next != nil {// 遍历到最后一个节点
        cur = cur.Next
    }
    newNode.Next = cur.Next
    cur.Next = newNode
    l.Size++
}


func (l *MyLinkedList) AddAtIndex(index int, val int)  {
    if index < 0 {
        index = 0
    } else if index > l.Size {// 题中 index == l.Size 会将该节点添加到链表末尾，所以是 l.Size 不是 l.Size -
        return
    }
    newNode := &SingleNode{Val: val}
    cur := l.DummyHead
    // cur 指向 index 的前一个节点
    for i := 0; i < index; i++ {
        cur = cur.Next
    }
    newNode.Next = cur.Next
    cur.Next = newNode
    l.Size++
}


func (l *MyLinkedList) DeleteAtIndex(index int)  {
    if index < 0 || index > l.Size - 1 {
        return
    }
    cur := l.DummyHead
    // 遍历到 index 的前一个节点
    for i := 0; i < index; i++ {
        cur = cur.Next
    }
    if cur.Next != nil {
        cur.Next = cur.Next.Next // 当前节点直接指向下下个节点，即删除了下一个节点
        l.Size--
    } else { // 链表中没有节点，DummyHead.Next == nil
        return
    }
}

自己思路写的单链表（烂）

思路很乱。虽然用到了虚拟头结点的思想，但是没有统一写法，每个函数想到哪写哪，逻辑不清晰，导致代码冗长。

特别体现在链表的遍历、循环边界、index合法边界上。

type SingleNode struct {
    Val int
    Next *SingleNode
}

type MyLinkedList struct {
    DummyHead *SingleNode
    Size int
}


func Constructor() MyLinkedList {
    NewDummyHead := &SingleNode {
        Val: -1,
        Next: nil,
    }

    return MyLinkedList{
        DummyHead: NewDummyHead,
        Size: 0,
    }
}


func (l *MyLinkedList) Get(index int) int {
    if l.Size < 1 {
        return -1
    }
    if index > l.Size - 1 || index < 0 {
        return -1
    } else {
        tmpNode := l.DummyHead
        for i := 0; i < l.Size; i++ {
            tmpNode = tmpNode.Next
            if i == index {
                return tmpNode.Val
            }
        }
    }
    return -1
}


func (l *MyLinkedList) AddAtHead(val int)  {
    newNode := &SingleNode{
    Val: val,
    Next: nil,
    }
    if l.Size == 0 {
        l.DummyHead.Next = newNode
        l.Size += 1
    } else if l.Size > 0 {
        // 找到第一个节点
        originalHead := l.DummyHead.Next
        newNode.Next = originalHead
        l.DummyHead.Next = newNode
        l.Size += 1
    }
}


func (l *MyLinkedList) AddAtTail(val int)  {
    newNode := &SingleNode{
    Val: val,
    Next: nil,
    }

    if l.Size == 0 {
        l.DummyHead.Next = newNode
        l.Size += 1
    } else if l.Size > 0 {
        tmpNode := l.DummyHead
        for i := 0; i < l.Size; i++ {
            tmpNode = tmpNode.Next
        }
        tmpNode.Next = newNode
        l.Size += 1
    }
}


func (l *MyLinkedList) AddAtIndex(index int, val int)  {
    if index == 0 {
        l.AddAtHead(val)
    } else if index == l.Size {
        l.AddAtTail(val)
    }else if index > 0 && index < l.Size {
        newNode := &SingleNode{
        Val: val,
        Next: nil,
        }
        // 找到 index 下标的节点
        var prevNode *SingleNode
        indexNode := l.DummyHead
        for i := 0; i < l.Size; i++ {
            indexNode = indexNode.Next
            if i == index - 1 {
                prevNode = indexNode
            }
            if i == index {
                break
            }
        }
        // 把 newNode 插入到 indexNode 前面
        // 先把 newNode 指向 indexNode
        newNode.Next = indexNode
        // 再把 prevNode 指向 newNode
        prevNode.Next = newNode
        l.Size += 1
    } else {// 非法 index 值
        return
    }
}


func (l *MyLinkedList) DeleteAtIndex(index int)  {
    // 如何避免操作空指针？
    if l.Size < 1 {
        return
    }
    if index == 0 {
        // 找到 indexNode, prevNode 就是 DummyHead
        // indexNode := l.DummyHead.Next
        l.DummyHead.Next = l.DummyHead.Next.Next
        l.Size -= 1
    } else if index > 0 && index <= l.Size - 1 {
        // 找到 prevNode 和 indexNode
        var prevNode *SingleNode
        indexNode := l.DummyHead
        for i := 0; i < l.Size; i++ {
            indexNode = indexNode.Next
            if i == index - 1 {
                prevNode = indexNode
            }
            if i == index {
                break
            }
        }
        prevNode.Next = indexNode.Next
        l.Size -= 1
    }
}


/**
 * 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);
 */

双链表（未完成）

代码随想录上的参考代码

//循环双链表
type MyLinkedList struct {
    dummy *Node
}

type Node struct {
    Val  int
    Next *Node
    Pre  *Node
}

//仅保存哑节点，pre-> rear, next-> head
/** Initialize your data structure here. */
func Constructor() MyLinkedList {
    rear := &Node{
        Val:  -1,
        Next: nil,
        Pre:  nil,
    }
    rear.Next = rear
    rear.Pre = rear
    return MyLinkedList{rear}
}

/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
func (this *MyLinkedList) Get(index int) int {
    head := this.dummy.Next
    //head == this, 遍历完全
    for head != this.dummy && index > 0 {
        index--
        head = head.Next
    }
    //否则, head == this, 索引无效
    if 0 != index {
        return -1
    }
    return head.Val
}

/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
func (this *MyLinkedList) AddAtHead(val int) {
    dummy := this.dummy
    node := &Node{
        Val: val,
        //head.Next指向原头节点
        Next: dummy.Next,
        //head.Pre 指向哑节点
        Pre: dummy,
    }

    //更新原头节点
    dummy.Next.Pre = node
    //更新哑节点
    dummy.Next = node
    //以上两步不能反
}

/** Append a node of value val to the last element of the linked list. */
func (this *MyLinkedList) AddAtTail(val int) {
    dummy := this.dummy
    rear := &Node{
        Val: val,
        //rear.Next = dummy(哑节点)
        Next: dummy,
        //rear.Pre = ori_rear
        Pre: dummy.Pre,
    }

    //ori_rear.Next = rear
    dummy.Pre.Next = rear
    //update dummy
    dummy.Pre = rear
    //以上两步不能反
}

/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
func (this *MyLinkedList) AddAtIndex(index int, val int) {
    head := this.dummy.Next
    //head = MyLinkedList[index]
    for head != this.dummy && index > 0 {
        head = head.Next
        index--
    }
    if index > 0 {
        return
    }
    node := &Node{
        Val: val,
        //node.Next = MyLinkedList[index]
        Next: head,
        //node.Pre = MyLinkedList[index-1]
        Pre: head.Pre,
    }
    //MyLinkedList[index-1].Next = node
    head.Pre.Next = node
    //MyLinkedList[index].Pre = node
    head.Pre = node
    //以上两步不能反
}

/** Delete the index-th node in the linked list, if the index is valid. */
func (this *MyLinkedList) DeleteAtIndex(index int) {
    //链表为空
    if this.dummy.Next == this.dummy {
        return
    }
    head := this.dummy.Next
    //head = MyLinkedList[index]
    for head.Next != this.dummy && index > 0 {
        head = head.Next
        index--
    }
    //验证index有效
    if index == 0 {
        //MyLinkedList[index].Pre = index[index-2]
        head.Next.Pre = head.Pre
        //MyLinedList[index-2].Next = index[index]
        head.Pre.Next = head.Next
        //以上两步顺序无所谓
    }
}

# 链表算法（1）