链表

理论基础

链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

链表的入口节点称为链表的头结点也就是head。

链表的类型

单链表：上面的就是单链表

双链表

每个节点有两个指针域，一个指向下一个节点，一个指向上一个节点
既可以向前查询也可以向后查询

循环链表

链表首尾相连
可以用来解决约瑟夫环问题

链表的存储方式

数组是在内存中是连续分布的，但链表在内存中不是连续分布的

链表是通过指针域的指针链接在内存中各个节点，所以链表中的节点在内存中不是连续分布的，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理

图中所示链表起始节点为2，终止节点为7，各个节点分布在内存的不同地址空间上，通过指针串联在一起

链表的定义

面试的时候，要自己手写链表

Go定义链表节点方式如下所示：

1
2
3
4
5


// 单链表
type ListNode struct {
    Val int        // 节点上存储的元素
    Next *ListNode // 指向下一个节点的指针
}

链表的操作

删除节点：删除D节点，如图所示：

只要将C节点的next指针指向E节点就可以了

添加节点

可以看出链表的增添和删除都是O(1)操作，不会影响到其他节点

但如果要删除最后一个节点，则需要从头节点查找到最后一个节点的前一个节点然后通过next指针进行删除操作，查找的时间复杂度是O(n)

性能分析

链表和数组的特性对比，如图所示：

数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组
链表的长度可以是不固定的，并且可以动态增删，适合数据量不固定，频繁增删，较少查询的场景

移除链表元素

203. 移除链表元素 - 力扣（LeetCode）

给定一个链表的头节点和一个目标值，删除链表中所有节点值为目标值的节点，返回新的头节点

由于本题头节点含值，所有为了保证操作统一性，添加虚拟头节点

从虚拟节点开始遍历，逐个检查当前节点的下一节点是否为目标值

注意：

保证当前节点不为空且当前节点的下一节点也不为空
若当前节点的下一节点是目标值，修改当前节点的指针域后，下已遍历仍从当前节点出发判断其下一节点
最后返回虚拟节点的指针域

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
    dummyHead := new(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 // 返回虚拟头节点的指针域
}

时间复杂度: O(n)
空间复杂度: O(1)

设计链表

707. 设计链表 - 力扣（LeetCode）

设计并实现自己的单/双链表：

若实现单链表，则节点应具备两个属性：val 和 next ，val 是当前节点的值，next 是指向下一个节点的指针/引用；若实现双向链表，则还需要属性 prev 以指示链表中的上一个节点
假设链表中的所有节点下标从 0 开始
链表定义、节点定义（自己写）、构造函数、获取节点值、添加头节点、添加尾节点、添加节点到指定节点前，删除节点

单链表

注意：

单链表节点可以不用定义，直接用ListNode复用力扣的全局变量，若想自己定义，可以定义节点名为Node

 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


type MyLinkedList struct {
    head   *ListNode
    length int
}

func Constructor() MyLinkedList {
    dummyNode := new(ListNode)
    myLinkedList := new(MyLinkedList)
    myLinkedList.head = dummyNode
    myLinkedList.length = 1
    return *myLinkedList
}

// 获取指定下标索引的节点值
func (this *MyLinkedList) Get(index int) int {
    index += 1       // 与添加虚拟头节点后的链表下标匹配
    cur := this.head // 定义当前节点为虚拟头节点
    for i := 0; i < this.length; i++ {
        if i == index { // 找到指定下标节点
            return cur.Val // 返回目标节点值
        }
        if cur.Next != nil {
            cur = cur.Next // 更新为下一节点
        } else {
            return -1 // 遍历到最后一个节点都未找到目标值
        }
    }
    return -1
}

// 添加头节点
func (this *MyLinkedList) AddAtHead(val int) {
    newNode := new(ListNode)
    newNode.Val = val
    if this.head.Next != nil { // 虚拟头节点后有节点
        newNode.Next = this.head.Next
        this.head.Next = newNode
    } else { // 虚拟头节点后无节点
        this.head.Next = newNode
        newNode.Next = nil
    }
    this.length++ // 更新链表长度
}

// 添加尾节点
func (this *MyLinkedList) AddAtTail(val int) {
    newNode := new(ListNode)
    newNode.Val = val
    newNode.Next = nil
    cur := this.head
    for i := 0; i < this.length-1; i++ { // 找到最后一个节点
        cur = cur.Next
    }
    cur.Next = newNode
    this.length++ // 更新链表长度
}

// 添加节点到指定索引节点之前
func (this *MyLinkedList) AddAtIndex(index int, val int) {
    if index == this.length-1 { // 刚好等于链表实际节点长度
        this.AddAtTail(val) // 插入尾节点
        return
    }
    newNode := new(ListNode)
    newNode.Val = val
    cur := this.head
    for cur != nil && cur.Next != nil { // 遍历链表
        if index == 0 { // 找到目标节点是当前节点的下一节点
            newNode.Next = cur.Next
            cur.Next = newNode
            this.length++ // 更新链表长度
            break
        }
        index-- // 更新索引
        cur = cur.Next
    }
}

// 删除指定下标节点
func (this *MyLinkedList) DeleteAtIndex(index int) {
    cur := this.head
    for cur != nil && cur.Next != nil {
        if index == 0 { // 找到目标节点是当前节点的下一节点
            cur.Next = cur.Next.Next
            this.length-- // 更新链表长度
            break
        }
        index-- // 更新索引
        cur = cur.Next
    }
}

时间复杂度: 涉及 index 的相关操作为 O(index)，其余为 O(1)
空间复杂度: O(n)

双向链表

  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
107


// 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--
}

时间复杂度: 涉及 index 的相关操作为 O(index)，其余为 O(1)
空间复杂度: O(n)

反转链表

206. 反转链表 - 力扣（LeetCode）

给定单链表的头节点 head ，返回反转后的链表

双指针，一个保存上一个节点，另一个遍历链表，边遍历边反转

反转：保存当前节点的下一个节点，将当前节点指向上一个节点，更新上一个节点为当前节点，当前节点前进

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


func reverseList(head *ListNode) *ListNode {
    var pre *ListNode // 保存上一个节点(结构体指针初始化为nil)
    cur := head       // 当前节点为头节点
    for cur != nil {  // 遍历到最后一个节点
        temp := cur.Next // 保存当前节点指针域
        cur.Next = pre   // 更新当前节点指针域
        pre = cur        // 更新保存的上一节点
        cur = temp       // 更新保存的当前节点
    }
    return pre
}

时间复杂度: O(n)
空间复杂度: O(1)

两两交换链表中的节点

24. 两两交换链表中的节点 - 力扣（LeetCode）

给定一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）

由于要返回头节点，所以定义虚拟头节点，保持操作统一性，也方便返回头节点

由于俩节点交换后还要更新这俩节点前面一个节点的指针域，所以用双指针

注意：先更新上一节点再更新当前节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


func swapPairs(head *ListNode) *ListNode {
    dummyNode := new(ListNode)
    dummyNode.Next = head
    cur := head                         // 从头节点出发
    pre := dummyNode                    // 保存上一节点为虚拟头节点
    for cur != nil && cur.Next != nil { // 遍历到倒数第二个节点
        temp := cur.Next         // 保存当前节点的下一个节点
        cur.Next = cur.Next.Next // 更新当前节点指针域
        temp.Next = cur          // 更新保存的当前节点的下一个节点的指针域
        pre.Next = temp          // 更新这俩节点的上一节点的指针域
        pre = cur                // 更新上一节点
        cur = cur.Next           // 更新当前节点
    }
    return dummyNode.Next
}

时间复杂度：O(n)
空间复杂度：O(1)

删除链表的倒数第 N 个结点

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

给定一个链表和整数n，删除链表的倒数第 n 个结点，并且返回链表的头结点

由于要返回头节点，所以定义虚拟头节点，保持操作统一性，也方便返回头节点

双指针法：先让快指针走n步，此时快慢指针之间距离为n。然后快慢指针同时移动，当快指针指向节点的下一个为 nil时，慢指针指向的节点的后一个节点就是要删除的节点。一遍遍历，时间复杂度为O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummyNode := new(ListNode)
    dummyNode.Next = head
    pre, cur := dummyNode, dummyNode
    for cur != nil {
        if cur.Next == nil { // 遍历到尾节点
            temp := pre.Next.Next // 保存要删除节点的下一节点
            pre.Next = temp       // 删除慢指针指向的下一节点
            break
        }
        if n != 0 {
            cur = cur.Next // 快指针前进
            n--
        } else {
            pre = pre.Next // 慢指针前进
            cur = cur.Next // 快指针前进
        }
    }
    return dummyNode.Next
}

时间复杂度：O(n)
空间复杂度：O(1)

链表相交

面试题 02.07. 链表相交

给定两个单链表的头节点 headA 和 headB ，返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null

双指针分别指向两个链表从平齐的地方同时开始遍历，当两个指针指向的节点相同时，则找到了相交的起始节点，当有至少一条链表遍历结束仍未找到，则返回nil

要先遍历两个链表求出长度，因为长链的指针要从与短链开头相同位置的节点出发才能保持同时前进

 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


func getIntersectionNode(headA, headB *ListNode) *ListNode {
    cur := headA
    lengthA, lengthB := 0, 0
    for cur != nil { // 遍历到尾节点
        lengthA++
        cur = cur.Next
    }
    cur = headB
    for cur != nil { // 遍历到尾节点
        lengthB++
        cur = cur.Next
    }
    differ := 0 // 俩链表长度差值
    longerList := max(lengthA, lengthB)
    idxA, idxB := headA, headB // 初始化俩指针分别指向头节点
    if longerList == lengthB { // B链表更长
        differ = lengthB - lengthA
        for ; differ != 0; differ-- { // 移动B链表指针到与A平齐
            idxB = idxB.Next
        }
    } else { // A链表更长
        differ = lengthA - lengthB
        for ; differ != 0; differ-- { // 移动A链表指针到与B平齐
            idxA = idxA.Next
        }
    }
    for idxA != idxB {
        if idxA == nil || idxB == nil { // 至少一个链表遍历结束
            return nil // 未找到公共节点
        }
        idxA = idxA.Next
        idxB = idxB.Next
    }
    return idxA
}

时间复杂度：O(n+m)
空间复杂度：O(1)

环形链表 II

142. 环形链表 II - 力扣（LeetCode）

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null

哈希表：定义一个哈希表逐个遍历节点，没遍历到一个节点就查字典，若查到则说明是环中回到起点，若遍历完都没查到则说明链中无环

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


func detectCycle(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return nil
    }
    cur := head
    nodeMap := make(map[*ListNode]bool)
    for cur != nil { // 逐个遍历到最后一个节点
        if _, ok := nodeMap[cur]; ok { // 遇到重复节点
            return cur
        }
        nodeMap[cur] = true // 将节点存入字典
        cur = cur.Next      // 遍历下一节点
    }
    return nil
}

时间复杂度：O(n)
空间复杂度：O(n)

快慢指针+数学：

判断是否有环：快指针先走两步，慢指针再走一步，重复此步骤；若链中无环，则始终无法相遇，快指针最终为nil；若有环，则慢指针最终会遇上指针，两个指针最终会在环中某节点相遇，因为相对于slow来说，fast是一个节点一个节点的靠近slow的，所以fast一定可以和slow重合

若有环如何找到环入口：

此时已经可以判断链表是否有环了，那么接下来要找这个环的入口了。

假设从头结点到环入口的节点数为x，环入口到俩指针相遇点的节点数为y，从相遇点再到环入口的节点数为 z

相遇时：

slow 指针走过的节点数为: x + y，
fast 指针走过的节点数：x + n (y + z) + y ，
n为fast指针在环内走了n圈才遇到slow指针， (y+z)为一圈的节点数

因为fast指针是一步走两个节点，slow 指针一步走一个节点，所以fast指针走过的节点数 = slow指针走过的节点数 * 2，得

x + y + n (y + z) = (x + y) * 2

两边消掉一个 (x+y) 得

n (y + z) = x + y

因为要找环形的入口，那么要求的是x

x = n (y + z) - y

再从n(y+z)中提出一个(y+z)，整理公式之后得

x = (n - 1) (y + z) + z

注意这里n ≥ 1的，因为fast指针至少要多走一圈才能相遇slow指针

这个公式的意义：

当n=1时，意味着fast指针在环形里转了一圈之后，就遇到了slow指针了

此时公式为 x = z，这就意味着，从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点，那么当这两个指针相遇的时候就是环形入口的节点

当n＞1时，意味着fast指针在环内转n圈之后才遇到slow指针

其实这种情况和n=1的效果是一样的，一样可以通过双指针法找到环形的入口节点，只不过index1指针在环里多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil { // 遍历到最后一个节点的前一个节点
        slow = slow.Next      //慢指针前进一步
        fast = fast.Next.Next // 快指针前进两步
        if slow == fast {     // 快慢指针相遇
            idx1 := slow       // 从相遇点出发
            idx2 := head       // 从链表头出发
            for idx1 != idx2 { // 俩指针每次前进一步
                idx1 = idx1.Next
                idx2 = idx2.Next
            }
            return idx1 // 俩指针相遇=>入环点
        }
    }
    return nil // 遍历链表无环
}

时间复杂度：O(n)
空间复杂度：O(1)