LeetCode 0707.设计链表

设计链表

题目描述

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


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

思路

题目要求

创建一个链表类，类中有构造器和五个方法：
- 获取链表第index个节点的数值
- 在链表的最前面插入一个节点
- 在链表的最后面插入一个节点
- 在链表第index个节点前面插入一个节点
- 删除链表的第index个节点

本题可采用单链表和双链表两种方式

单链表是最简单的一种，它提供了在常数时间内的 addAtHead 操作和在线性时间内的 addAtTail 的操作。

双链表是最常用的一种，因为它提供了在常数时间内的 addAtHead 和 addAtTail 操作，并且优化了插入和删除。

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

为了使插入和删除时间消耗更少，我使用双链表；为了简化插入和删除，我在头节点前加入一个伪头。

注意

Go 语言中没有类（Class）的概念，但可以使用结构体（Structs）对属性进行封装，结构体就像是类的一种简化形式
Go 方法是作用在接收者（Receiver）上的一个函数，接收者是某种类型的变量。因此方法是一种特殊类型的函数。

定义方法的格式如下：
1

func (recv receiver_type) methodName(parameter_list) (return_value_list) { ... }
Go语言中没有提供构造函数相关的特殊机制，用户根据自己的需求，将参数使用函数传递到结构体构造参数中即可完成构造函数的任务。
index从0开始
在添加节点后size++，删除节点后size--

代码

Go

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106


// MyLinkedList 双链表(类)
type MyLinkedList struct {
    size      int
    dummyHead *Node
    dummyTail *Node
}

// Node 节点(结构体)
type Node struct {
    value int
    pre   *Node
    next  *Node
}

// Constructor 构造方法
func Constructor() MyLinkedList {
    dummyHead := new(Node)
    dummyTail := new(Node)
    dummyHead.next = dummyTail
    dummyTail.pre = dummyHead
    return MyLinkedList{0, dummyHead, dummyTail}
}

// GetNode 获取链表index号节点
func (this *MyLinkedList) GetNode(index int) *Node {
    p := this.dummyHead.next
    if index <= (this.size >> 1) {
        // 从前遍历
        for i := 0; i < index; i++ {
            p = p.next
        }
    } else {
        // 从后遍历
        p = this.dummyTail.pre
        for i := 0; i < this.size-1-index; i++ {
            p = p.pre
        }
    }
    return p
}

// Get 获取链表index号节点的数值
func (this *MyLinkedList) Get(index int) int {
    if index < 0 || index >= this.size {
        // 索引无效
        return -1
    }
    return this.GetNode(index).value
}

// AddAtHead 在链表的最前面插入一个节点
func (this *MyLinkedList) AddAtHead(val int) {
    head := new(Node)
    head.value = val
    head.pre = this.dummyHead
    head.next = this.dummyHead.next
    this.dummyHead.next = head
    head.next.pre = head
    this.size++
}

// AddAtTail 在链表的最后面插入一个节点
func (this *MyLinkedList) AddAtTail(val int) {
    tail := new(Node)
    tail.value = val
    tail.pre = this.dummyTail.pre
    tail.next = this.dummyTail
    this.dummyTail.pre = tail
    tail.pre.next = tail
    this.size++
}

// AddAtIndex 在链表index号节点前面插入一个节点
func (this *MyLinkedList) AddAtIndex(index int, val int) {
    if index < 0 {
        // 在链表的最前面插入一个节点
        this.AddAtHead(val)
        return
    }
    if index == this.size {
        this.AddAtTail(val)
        return
    }
    if index > this.size {
        return
    }
    indexNode := this.GetNode(index)
    newNode := new(Node)
    newNode.value = val
    newNode.pre = indexNode.pre
    newNode.next = indexNode
    indexNode.pre = newNode
    newNode.pre.next = newNode
    this.size++
}

func (this *MyLinkedList) DeleteAtIndex(index int) {
    if index < 0 || index >= this.size {
        // 索引无效
        return
    }
    indexNode := this.GetNode(index)
    indexNode.pre.next = indexNode.next
    indexNode.next.pre = indexNode.pre
    this.size--
}

Link

GitHub