本文由 简悦 SimpRead 转码， 原文地址 programmercarl.com

707 力扣题目链接 (opens new window)，难度：中等

题意

设计链表的实现。您可以选择使用单链表或双链表。
单链表中的节点应该具有两个属性：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
提示：

  • 所有val值都在 [1, 1000] 之内。
  • 操作次数将在 [1, 1000] 之内。
  • 请不要使用内置的 LinkedList 库。


    分析

    链表是一个包含零个或多个元素的数据结构。每个元素都包含一个值和到另一个元素的链接。根据链接数的不同，可以分为单链表，双链表和多重链表。

单链表是最简单的一种，它提供了在常数时间内的 addAtHead 操作和在线性时间内的 addAtTail 的操作。
双链表是最常用的一种，因为它提供了在常数时间内的 addAtHead 和 addAtTail 操作，并且优化的插入和删除。
双链表在 Java 中的实现为 LinkedList，在 Python 中为 list
[

](https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html)

链表操作的两种方式：

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

哨兵节点在树和链表中被广泛用作伪头、伪尾等，通常不保存任何数据。来简化插入和删除

详细的见：
移除链表元素

方法1：双向循环链表+哨兵

双链表比单链表快得多，测试用例花费的时间比单链表快了两倍。但是它更加复杂，它包含了 size，记录链表元素个数，和伪头伪尾。

伪头和伪尾总是存在，MyLinkedList 中所有节点都包含：值 + 指向前一个节点的指针 + 指向后一个节点的指针。

addAtIndex，addAtHead 和 addAtTail：

找到要插入节点的前驱节点和后继节点。如果要在头部插入节点，则它的前驱结点是伪头。如果要在尾部插入节点，则它的后继节点是伪尾。
通过改变前驱结点和后继节点的链接关系添加元素。

addAtHead代码步骤分析

  2. 循环嵌套的代码和递归一样，很复杂，不要试图用人脑去走每一步的流程。只需要理解步骤，自己也可以写出流程，这个流程写出来是很费脑的，因为都是循环嵌套。只需要写一次理解就好了。以后写的时候，只需要按照步骤写代码就行，不需要再次试图用人脑去走每一步。费时间。
  3. 就像从规律中发现一个公式，以后只需要用公式就行，不必再次推导公式了
  5. 第一次增加3：
  6. MyLinkedList={
  7.     Dummy:{
  8.         Val:  -1,
  9.         Next: Dummy
  10.         Pre:  Dummy,
  11.     }
  12. }
  15. 链表头部增加值：3
  16. // 1 给新头节点的next为原头节点，pre为虚拟节点：
  17. node={
  18.     Val"3,
  19.     Next:Dummy.Next
  20.     Pre:Dummy
  21. }
  23. // 2 将原头节点的pre改为新的头结点：
  24. // Dummy.Next.Pre = node，此时上面node中的值也变了；在初始化节点的时候，Dummy.Next==Dummy，所以就是将dummy中的pre改为了node
  25. // 只有第一次添加节点的时候，刚好吧dummy的per也改为了尾结点，以后再头部增加节点的时候，dummy的pre还是第一次添加节点的值，这个值就变成尾结点了。巧妙的进行了首尾相连
  26.     Dummy:{
  27.         Val:  -1,
  28.         Next: {
  29.             Val:  -1,
  30.             Next: Dummy,
  31.             Pre:  node
  32.         }
  33.         Pre: node
  34.     }
  36. // 3 将虚拟节点的next改为新的头节点
  37. // Dummy.Next = node，同时修改上面node.Next的值为新node
  38.     Dummy:{
  39.         Val:  -1,
  40.         Next: node={
  41.                 Val"3,
  42.                 Next:{
  43.                     Val:  -1,
  44.                     Next: Dummy,
  45.                     Pre:  node
  46.                 }
  47.                 Pre: Dummy
  48.             }
  49.         Pre:  node
  50.     }
  57. 增加2
  58.     Dummy:{
  59.         Val:  -1,
  60.         Next: node={
  61.                 Val"3,
  62.                 Next:{
  63.                     Val:  -1,
  64.                     Next: Dummy,
  65.                     Pre:  node
  66.                 }
  67.                 Pre: Dummy
  68.             }
  69.         Pre:  node
  70.     }
  73. // 1 给新头节点的next为原头节点，pre为虚拟节点：
  74. node={
  75.     Val"2,
  76.     Next:Dummy.Next
  77.     Pre:Dummy
  78. }
  80. // 2 将原头节点的pre改为新的头结点：
  81. // Dummy.Next.Pre = node，此时上面node中的值也变了；
  82.     Dummy:{
  83.         Val:  -1,
  84.         Next: node={
  85.                 Val"3,
  86.                 Next:{
  87.                     Val:  -1,
  88.                     Next: Dummy,
  89.                     Pre:  node
  90.                 }
  91.                 Pre: node
  92.             }
  93.         Pre:  node
  94.     }
  96. // 3 将虚拟节点的next改为新的头节点
  97. // Dummy.Next = node，同时修改上面node.Next的值为新node
  98.     Dummy:{
  99.         Val:  -1,
  100.         Next: node={
  101.                 Val"2,
  102.                 Next:node={
  103.                         Val"3,
  104.                         Next:{
  105.                             Val:  -1,
  106.                             Next: Dummy,
  107.                             Pre:  node
  108.                         }
  109.                         Pre: node
  110.                     }
  111.                 Pre: Dummy
  112.             }
  113.         Pre:  node
  114.     }

deleteAtIndex：

和插入同样的道理。

  • 找到要删除节点的前驱结点和后继节点。
  • 通过改变前驱结点和后继节点的链接关系删除元素。

get：

  • 通过比较 index 和 size - index 的大小判断从头开始较快还是从尾巴开始较快。
  • 从较快的方向开始。

复杂度分析

  • 时间复杂度：
    • addAtHead，addAtTail： O(1)
    • get，addAtIndex，delete：O(min(k,N−k))，其中 k 指的是元素的索引。
  • 空间复杂度：所有的操作都是 O(1)。

    Go：

/**
 * 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 {
    // 申明指针，指向 Node结构体 的指针
    dummy *Node //定义一个虚拟头结点，
}

// 定义链表节点结构体
type Node struct {
    Val  int
    Next *Node
    Pre  *Node
}

// go语言没有面向对象。没有析构函数；力扣规定，程序会先执行Constructor函数进行初始化工作
// 初始化链表，是双向循环链表，首尾相连
// 此时结构体MyLinkedList为：Dummy:rear{Val:  -1,Next: rear,Pre:  rear,} 嵌套自身的结构体是无限循环的，无法直接打印，循环遍历的话也是无限值
// 但是只要判断Dummy.Next是否和Dummy相等，就可以知道Dummy.Next是否是空的节点，从而终止循环。
func Constructor() MyLinkedList {
    rear := &Node{
        Val:  -1,
        Next: nil,
        Pre:  nil,
    }
    rear.Next = rear
    rear.Pre = rear
    return MyLinkedList{rear}// 给结构体顺序赋值，不用写键名Dummy: rear
}


// 函数方法：给结构体MyLinkedList绑定函数
// get(index)：获取链表中第 index 个节点的值（从0开始）。如果索引无效，则返回 - 1。
// 如原链表为：Dummy<->1<->2<->3<->4，index=2，找到3
// 1 过滤掉虚拟节点 1<->2<->3<->4
// 2 遍历链表，如果index为负数，返回-1；如果index=0，就是头结点的值；
func (this *MyLinkedList) Get(index int) int {
    head := this.dummy.Next // 虚拟头节点的next为真正的头结点开始的地方

    // 遍历链表
    //head == this.Dummy, 说明Dummy和head都是同一个Node空节点，说明head为空节点了，没有后续的节点了。
    for head != this.dummy && index > 0 {
        index-- // 第n个链表的值，只能遍历获取，每次-1就，直到index=0就能找到第n个节点的值(前提是索引index有效，没超出链表的大小)
        head = head.Next // head.Next 为下一个节点
    }

    // 如果链表只有5个值，参数index的值最大为4（索引从0开始），如果参数index=5；最后发现下一个节点为空了，此时index=1，有效的索引index最后应该为0
    // 遍历完链表后，index不等于1；就是无效的索引，超出链表的大小了；规定返回-1即可
    if 0 != index {
        return -1
    }
    // 索引有效的情况，返回查到的链表值
    return head.Val
}


// 链表头部增加值：
// 依次增加3，2，1到头结点，链表为：3<->Dummy<->1<->2<->3
func (this *MyLinkedList) AddAtHead(val int) {
    dummy := this.dummy// 虚拟头节点

    // 1 给新头节点的next为原头节点，pre为虚拟节点：
    node := &Node{
        Val: val, // 3

        Next: dummy.Next, // 3->-1，Dummy.Next为真正的头结点。将其放在新的头结点后面；如果第一次添加值，Dummy.next是空的，

        Pre: dummy, // -1<- 3 ->-1 头节点的上一个节点总是虚拟节点
    }

    // 2 将原头节点的pre改为新的头结点：
    // 上面node.Next.pre的值也修改为node了
    dummy.Next.Pre = node

    // 3 将虚拟节点的next改为新的头节点
    //此时的node,已经把上面的结果包含了，也就是node.next。pre=node；此时把拼接好的node，放在虚拟节点的后面即可。
    dummy.Next = node

}


// 链表尾部添加值
// 如原链表为：Dummy<->1<->2<->3；将4添加到尾部
func (this *MyLinkedList) AddAtTail(val int) {
    dummy := this.dummy

    // 1 给尾节点的next为空节点，这里可以是Dummy节点，因为它就是空节点；pre为
    rear := &Node{
        Val: val,

        Next: dummy,// 尾节点的下一个是虚拟dummy节点，首尾相连

        Pre: dummy.Pre,// 尾结点的上一个是原尾结点，dummy的pre就是尾结点。
    }

    // 2原尾结点的下一个为 新的尾节点
    dummy.Pre.Next = rear
    // 虚拟节点的上一个为新的尾节点。
    dummy.Pre = rear

}


//在链表中的第 index 个节点之前添加值为 val  的节点。
//如果 index 等于链表的长度，则该节点将附加到链表的末尾。(正常逻辑满足条件)
//如果 index 大于链表长度，则不会插入节点。（判断）
//如果 index 小于 0，则在头部插入节点。 （index小于0，head就是头结点，满足）
func (this *MyLinkedList) AddAtIndex(index int, val int) {
    head := this.dummy.Next

    for head != this.dummy && index > 0 {
        head = head.Next
        index--
    }

    // 如果index大于0，说明超出链表长度，不操作
    if index > 0 {
        return
    }

    // 插入的节点的前后关系。
    node := &Node{
        Val: val,

        Next: head,

        Pre: head.Pre,
    }
    // 前面节点的下一个为新节点
    head.Pre.Next = node
    // 后面的节点上一个为新的节点。
    head.Pre = node

}


//如果索引 index 有效，则删除链表中的第 index 个节点。
func (this *MyLinkedList) DeleteAtIndex(index int) {
    //空链表，直接返回
    if this.dummy.Next == this.dummy {
        return
    }
    //头节点
    head := this.dummy.Next

    for head.Next != this.dummy && index > 0 {
        head = head.Next
        index--
    }
    //只有index等于0，说明索引有效；大于0说明超出链表长度，
    if index == 0 {
        // 1将要删除的节点的下一个的pre为：要删除的节点的上一个
        head.Next.Pre = head.Pre
        // 2将要删除的节点的上一个的下一个为：要删除的节点的下一个。
        head.Pre.Next = head.Next

    }
}

go-本地可运行

package main

import (
    "fmt"
)

type MyLinkedList struct {
    // 申明指针，指向 Node结构体 的指针
    Dummy *Node //定义一个虚拟头结点，
}

// 定义链表节点结构体
type Node struct {
    Val  int
    Next *Node
    Pre  *Node
}

func main() {
    var ml = Constructor()
    fmt.Printf("ml=%+v\n", ml)                                 // ml={Dummy:0xc0000a6020}
    fmt.Printf("ml.Dummy=%+v\n", ml.Dummy)                     // ml.Dummy=&{Val:-1 Next:0xc00000c080 Pre:0xc00000c080}
    fmt.Printf("ml.Dummy.Next=%+v\n", ml.Dummy.Next)           // ml.Dummy.Next=&{Val:-1 Next:0xc0000a6020 Pre:0xc0000a6020}
    fmt.Printf("ml.Dummy.Next.Next=%+v\n", ml.Dummy.Next.Next) // ml.Dummy.Next.Next=&{Val:-1 Next:0xc00011c020 Pre:0xc00011c020}

    //bs, _ := json.Marshal(ml)
    //var out bytes.Buffer
    //json.Indent(&out, bs, "", "\t")
    //fmt.Printf("MyLinkedList=%v\n", out.String())

    fmt.Printf("初始虚拟头结点 Dummy=%+v\n", ml.Dummy.Val) // Dummy=-1

    fmt.Printf("初始获取Get index=1:%+v\n", ml.Get(1)) // Get:-1

    fmt.Println("AddAtHead 3")
    ml.AddAtHead(3)
    fmt.Printf("ml.Dummy.Pre.Val=%+v\n", ml.Dummy.Pre.Val)   // ml.Dummy.Pre.Val=3
    fmt.Printf("ml.Dummy.Next.Val=%+v\n", ml.Dummy.Next.Val) // ml.Dummy.Next.Val=3

    fmt.Println("AddAtHead 2")
    ml.AddAtHead(2)
    fmt.Printf("ml.Dummy.Pre.Val=%+v\n", ml.Dummy.Pre.Val)   // ml.Dummy.Pre.Val=3
    fmt.Printf("ml.Dummy.Next.Val=%+v\n", ml.Dummy.Next.Val) // ml.Dummy.Next.Val=2

    fmt.Println("AddAtHead 1")
    ml.AddAtHead(1)
    fmt.Printf("ml.Dummy.Pre.Val=%+v\n", ml.Dummy.Pre.Val)   // ml.Dummy.Pre.Val=3
    fmt.Printf("ml.Dummy.Next.Val=%+v\n", ml.Dummy.Next.Val) // ml.Dummy.Next.Val=1

    fmt.Printf("Get index=-1:%+v\n", ml.Get(-1)) // Get:-1
    fmt.Printf("Get index=0:%+v\n", ml.Get(0))   // Get:-1
    fmt.Printf("Get index=1:%+v\n", ml.Get(1))   // Get:-1
    fmt.Printf("Get index=2:%+v\n", ml.Get(2))   // Get:-1
    fmt.Printf("Get index=3:%+v\n", ml.Get(3))   // Get:-1

}

// go语言没有面向对象。没有析构函数；力扣规定，程序会先执行Constructor函数进行初始化工作
// 初始化链表，是双向循环链表，首尾相连
// 此时结构体MyLinkedList为：Dummy:rear{Val:  -1,Next: rear,Pre:  rear,} 嵌套自身的结构体是无限循环的，无法直接打印，循环遍历的话也是无限值
// 但是只要判断Dummy.Next是否和Dummy相等，就可以知道Dummy.Next是否是空的节点，从而终止循环。
func Constructor() MyLinkedList {
    rear := &Node{
        Val:  -1,
        Next: nil,
        Pre:  nil,
    }
    rear.Next = rear
    rear.Pre = rear
    return MyLinkedList{rear} // 给结构体顺序赋值，不用写键名Dummy: rear
}

// 函数方法：给结构体MyLinkedList绑定函数
// get(index)：获取链表中第 index 个节点的值（从0开始）。如果索引无效，则返回 - 1。
// 如原链表为：Dummy<->1<->2<->3<->4，index=2，找到3
// 1 过滤掉虚拟节点 1<->2<->3<->4
// 2 遍历链表，如果index为负数，返回-1；如果index=0，就是头结点的值；
func (this *MyLinkedList) Get(index int) int {
    head := this.Dummy.Next // 虚拟头节点的next为真正的头结点开始的地方

    // 遍历链表
    //head == this.Dummy, 说明Dummy和head都是同一个Node空节点，说明head为空节点了，没有后续的节点了。
    for head != this.Dummy && index > 0 {
        index--          // 第n个链表的值，只能遍历获取，每次-1就，直到index=0就能找到第n个节点的值(前提是索引index有效，没超出链表的大小)
        head = head.Next // head.Next 为下一个节点
    }
    // 如果链表只有5个值，参数index的值最大为4（索引从0开始），如果参数index=5；最后发现下一个节点为空了，此时index=1，有效的索引index最后应该为0
    // 遍历完链表后，index不等于1；就是无效的索引，超出链表的大小了；规定返回-1即可
    if index != 0 {
        return -1
    }
    // 索引有效的情况，返回查到的链表值
    return head.Val
}

// 链表头部增加值：
// 依次增加3，2，1到头结点，链表为：3<->Dummy<->1<->2<->3
func (this *MyLinkedList) AddAtHead(val int) {
    Dummy := this.Dummy // 虚拟头节点

    // 1 给新头节点的next为原头节点，pre为虚拟节点：
    node := &Node{
        Val: val, // 3

        Next: Dummy.Next, // 3->-1，Dummy.Next为真正的头结点。将其放在新的头结点后面；如果第一次添加值，Dummy.next是空的，

        Pre: Dummy, // -1<- 3 ->-1 头节点的上一个节点总是虚拟节点
    }

    // 2 将原头节点的pre改为新的头结点：
    // 上面node.Next.pre的值也修改为node了
    Dummy.Next.Pre = node
    // 3 将虚拟节点的next改为新的头节点
    //此时的node,已经把上面的结果包含了，也就是node.next。pre=node；此时把拼接好的node，放在虚拟节点的后面即可。
    Dummy.Next = node
}

// 链表尾部添加值
// 如原链表为：Dummy<->1<->2<->3；将4添加到尾部
func (this *MyLinkedList) AddAtTail(val int) {
    Dummy := this.Dummy

    // 1 给尾节点的next为空节点，这里可以是Dummy节点，因为它就是空节点；pre为
    rear := &Node{
        Val: val,

        Next: Dummy, // 尾节点的下一个是虚拟dummy节点，首尾相连

        Pre: Dummy.Pre, // 尾结点的上一个是原尾结点，dummy的pre就是尾结点。
    }

    // 2原尾结点的下一个为 新的尾节点
    Dummy.Pre.Next = rear
    // 虚拟节点的上一个为新的尾节点。
    Dummy.Pre = rear

}

//在链表中的第 index 个节点之前添加值为 val  的节点。
//如果 index 等于链表的长度，则该节点将附加到链表的末尾。(正常逻辑满足条件)
//如果 index 大于链表长度，则不会插入节点。（判断）
//如果 index 小于 0，则在头部插入节点。 （index小于0，head就是头结点，满足）
func (this *MyLinkedList) AddAtIndex(index int, val int) {
    head := this.Dummy.Next

    for head != this.Dummy && index > 0 {
        head = head.Next
        index--
    }
    // 如果index大于0，说明超出链表长度，不操作
    if index > 0 {
        return
    }
    // 插入的节点的前后关系。
    node := &Node{
        Val:  val,
        Next: head,
        Pre:  head.Pre,
    }
    // 前面节点的下一个为新节点
    head.Pre.Next = node
    // 后面的节点上一个为新的节点。
    head.Pre = node

}

//如果索引 index 有效，则删除链表中的第 index 个节点。
func (this *MyLinkedList) DeleteAtIndex(index int) {
    //空链表，直接返回
    if this.Dummy.Next == this.Dummy {
        return
    }
    //头节点
    head := this.Dummy.Next
    //
    for head.Next != this.Dummy && index > 0 {
        head = head.Next
        index--
    }
    //只有index等于0，说明索引有效；大于0说明超出链表长度，
    if index == 0 {
        // 1将要删除的节点的下一个的pre为：要删除的节点的上一个
        head.Next.Pre = head.Pre
        // 2将要删除的节点的上一个的下一个为：要删除的节点的下一个。
        head.Pre.Next = head.Next

    }
}

方法2：单链表+哨兵

哨兵节点被用作伪头，这样MyLinkedList 中所有节点均包含：值 + 链接到下一个元素的指针。

addAtIndex，addAtHead 和 addAtTail：

我们首先讨论 addAtIndex，因为伪头的关系， addAtHead 和 addAtTail 可以使用 addAtIndex 来完成。

找到要插入位置节点的前驱节点。如果要在头部插入，则它的前驱节点就是伪头。如果要在尾部插入节点，则前驱节点就是尾节点。
通过改变 next 来插入节点。

deleteAtIndex：

和插入同样的道理。

  • 找到要删除节点的前驱节点。
  • 通过改变 next 来删除节点。

get(index)

从伪头节点开始，向前走 index+1 步。

复杂度分析

  • 时间复杂度：
    • addAtHead： O(1)
    • addAtInder，get，deleteAtIndex: O(k)，其中 k 指的是元素的索引。
    • addAtTail：O(N)，其中 N 指的是链表的元素个数。
  • 空间复杂度：所有的操作都是 O(1)。