注意

leetcode707设计链表
双链表与单链表不同的地方:他有了pre,可以在当前节点指向上一个节点,有了更多的可玩性,
记住,特殊情况是头结点,尾接点,
特殊的小细节是,究竟node.Next!=nil还是node!=nil还是node.Next!=nil&&node!=nil
如果在中间位置。一定要让pre和next形成闭环。

code

type DoubleLinkNode struct{
    Value int
    Pre *DoubleLinkNode
    Next *DoubleLinkNode
}

type MyLinkedList struct{
    Lens int
    Head *DoubleLinkNode
}

func Constructor()MyLinkedList{
    return MyLinkedList{
        Head: nil,
        Lens: 0,
    }
}

// Get 获取指定索引位置值
func (this *MyLinkedList)Get(index int)int{
    // 判断索引
    if index<0||index>this.Lens-1{
        return -1
    }
    node := this.Head
    for index>0{
        index--
        node = node.Next
    }
    return node.Value
}

// AddAtTail 尾插
func (this *MyLinkedList) AddAtTail(val int){
    // 先判断长度
    if this.Lens<1{
        this.AddAtHead(val)
        return
    }
    node := this.Head
    // 遍历到尾
    for node.Next!=nil{
        node = node.Next
    }
    tail := &DoubleLinkNode{
        Value: val,
        Pre:   node,
        Next:  nil,
    }
    node.Next = tail
    this.Lens++
}

// AddAtIndex 在指定索引位置添加
func (this *MyLinkedList) AddAtIndex(index int, val int){
    // 如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
    if index == this.Lens{
        this.AddAtTail(val)
        return
    }
    if index>this.Lens-1{
        return
    }
    if index<0{
        this.AddAtHead(val)
        return
    }
    // 上面的三个、if是题目要求
    // 还有一个情况,index==0;剩下的就是自己人了
    node := this.Head
    if index==0{
        this.Head = &DoubleLinkNode{
            Value: val,
            Pre:   nil,
            Next:  node,
        }
        if this.Head.Next != nil{
            this.Head.Next.Pre = this.Head
        }
        this.Lens++
        return
    }
    for index>0{
        index--
        node = node.Next
    }
    //fmt.Println("add at index:", node.Value)
    bak := node.Pre

    newNode := &DoubleLinkNode{
        Value: val,
        Pre:   bak,
        Next:  node,
    }
    node.Pre = newNode
    // 上一个节点的下一个要指向新插入节点
    bak.Next = newNode
    this.Lens++
}

// AddAtHead 在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。
func (this *MyLinkedList) AddAtHead(val int){
    node := this.Head
    if this.Lens<1{
        this.Head = &DoubleLinkNode{
            // 注意前后节点都是nil
            Value: val,
            Pre:   nil,
            Next:  nil,
        }
        this.Lens++
    }else{
        this.Head = &DoubleLinkNode{
            Value: val,
            Pre:   nil,
            Next:  node,
        }
        // 下一个节点别忘了指向头部,此处是一定有下一个节点的
        node.Pre = this.Head
        this.Lens++
    }
}

// DeleteAtIndex 删除指定索引位置元素
func (this *MyLinkedList) DeleteAtIndex(index int){
    // 如果索引 index 有效,则删除链表中的第 index 个节点
    if index<0||index>this.Lens-1{
        return
    }
    node := this.Head
    // 索引等于0
    if index==0{
        this.Head = node.Next
        this.Lens--
        return
    }
    // 索引不等于0
    for index>0{
        index--
        node = node.Next
    }
    node.Pre.Next = node.Next
    // 这里很容易忘记写。需要画图,此处判断的的目的是,为了防止删除的是最后一个节点,调用.pre报错空指针
    if node.Next!=nil{
        node.Next.Pre = node.Pre
    }
    this.Lens--
}

// ToString 格式化输出
func (this *MyLinkedList) ToString()string{
    node := this.Head
    str := ""
    for node!=nil{
        str += fmt.Sprintf("%v-->", node.Value)
        node = node.Next
    }
    str += fmt.Sprintf("nil")
    fmt.Println(str)
    return str
}

改进一下头插的代码:

    bak := this.Head
    fmt.Println("bak:", bak)
    this.Head = &DoubleLinkNode{
        Value: val,
        Pre:   nil,
        Next:  bak,
    }
    if this.Head.Next!=nil{
        this.Head.Next.Pre = this.Head
    }
    this.Lens++

原理,先备份头结点。bak := this.Head
这时bak可能为nil
让头结点指针指向新添加的节点,同时他的next指向bak

    if this.Head.Next!=nil{
        this.Head.Next.Pre = this.Head
    }

这样判断一下,看this.head.next是否为空,如果为空的话那么说明链表中只有一个节点。这时如果贸然调用this.Head.Next.Pre = this.Head会报空指针异常

分类: go算法

2 条评论

猪猪 · 2021-11-19 22:46

想你

    xiaosheng · 2021-11-20 16:47

    哈哈哈,me too

评论已关闭。

站点统计

  • 文章总数:315 篇
  • 分类总数:20 个
  • 标签总数:193 个
  • 运行天数:1147 天
  • 访问总数:26858 人次

浙公网安备33011302000604

辽ICP备20003309号