链表

理论基础

链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向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)

思路二：双指针

保证两个指针走过的路径长度相同：结束的一方，让其从另一条链头继续；相当于每个指针最终都走过一遍两条链；最终两指针走过路径长度相同，若两链无焦点，则两指针最终都会为空，若有焦点，则会在焦点相遇

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


func getIntersectionNode(headA, headB *ListNode) *ListNode {
    l1, l2 := headA, headB
    for l1 != l2 {
        if l1 != nil {
            l1 = l1.Next
        } else {
            l1 = headB
        }
        if l2 != nil {
            l2 = l2.Next
        } else {
            l2 = headA
        }
    }
    return l1
}

时间复杂度：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)

附加

删除排序链表中的重复元素

83. 删除排序链表中的重复元素 - 力扣（LeetCode）

方法一：单指针逐个删除重复节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


func deleteDuplicates(head *ListNode) *ListNode {
    cur := head
    for cur != nil {
        for cur.Next != nil && cur.Val == cur.Next.Val {
            cur.Next = cur.Next.Next
        }
        cur = cur.Next
    }
    return head
}

方法二：双指针找到新元素后一次性删除中间的重复节点

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


func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    pre := head
    cur := head.Next
    for cur != nil {
        for cur != nil && cur.Val == pre.Val {
            cur = cur.Next
        }
        pre.Next = cur
        if cur == nil {
            break
        }
        pre = cur
        cur = cur.Next
    }
    return head
}

附加

删除排序链表中的重复元素 II

82. 删除排序链表中的重复元素 II - 力扣（LeetCode）

只要有元素重复，就将该元素全部删除

链表头结点可能被删除，所以要用 dummy node 辅助删除逻辑一致
若当前元素与下一元素相同，则当前指针后移不断寻找相同元素，直到当前元素与下一元素不同；
此时注意要区分是有重复元素的不同，还是无重复元素的不同：若有重复元素，则删除重复元素，前一元素指针不动；若无重复元素，则更新前一元素指针；
最后更新当前元素指针为前一元素指针的下一个

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


func deleteDuplicates(head *ListNode) *ListNode {
    dummyNode := &ListNode{Val: -101, Next: head}
    pre, cur := dummyNode, dummyNode.Next
    for cur != nil {
        findDup := false
        for cur.Next != nil && cur.Val == cur.Next.Val {
            findDup = true
            cur = cur.Next
        }
        if findDup {
            // 有重复元素:删除重复元素
            pre.Next = cur.Next
        } else {
            // 无重复元素:更新前一元素指针
            pre = pre.Next
        } 
        // 更新当前元素指针为前一元素指针的下一个
        cur = pre.Next
    }
    return dummyNode.Next
}

反转链表 II

92. 反转链表 II - 力扣（LeetCode）

反转给定位置的链表节点

为了处理头节点是起始点的情况，引入虚拟头节点指向头节点
遍历节点至指定结束位置，记录反转起始和结束点，以及起始前一个和结束后一个节点；
反转指定链表节点后，重新连接起始前一个和结束后一个节点
遇到只有一个头节点或反转一个节点的情况直接返回

 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


func reverseBetween(head *ListNode, left int, right int) *ListNode {
    if head.Next == nil || left == right {
        return head
    }
    dummyNode := &ListNode{Next: head}
    end := dummyNode
    var preS, start, nextE *ListNode
    for i := 0; i < right; i++ {
        // 记录反转的起始节点和其前一个节点
        if i == left-1 {
            preS = end
            start = end.Next
        }
        end = end.Next
    }
    // 记录反转的最后一个节点的下一个节点
    nextE = end.Next
    reverse(start, nextE)
    preS.Next = end
    start.Next = nextE
    return dummyNode.Next
}
func reverse(head, nextE *ListNode) {
    var pre *ListNode
    cur := head
    for cur != nextE {
        temp := cur.Next
        cur.Next = pre
        pre = cur
        cur = temp
    }
}

合并两个有序链表

21. 合并两个有序链表 - 力扣（LeetCode）

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


func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummyNode := new(ListNode)
    pre := dummyNode
    // 遍历两个链表直到一条结束
    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            pre.Next = list1
            list1 = list1.Next
        } else {
            pre.Next = list2
            list2 = list2.Next
        }
        pre = pre.Next
    }
    // 将剩下的链表直接连接到最后面
    if list1 == nil {
        pre.Next = list2
    } else {
        pre.Next = list1
    }
    return dummyNode.Next
}

分隔链表

86. 分隔链表 - 力扣（LeetCode）

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


func partition(head *ListNode, x int) *ListNode {
    // 两个链表的虚拟头节点:一个小于目标值,一个大于等于目标值的
    dummyNode1, dummyNode2 := new(ListNode), new(ListNode)
    list1, list2 := dummyNode1, dummyNode2
    // 得到两个链表:一个小于目标值,一个大于等于目标值
    for head != nil {
        if head.Val < x {
            list1.Next = head
            list1 = list1.Next
        } else {
            list2.Next = head
            list2 = list2.Next
        }
        head = head.Next
    }
    // 将大于目标值的链表的末节点NEXT域置空
    list2.Next = nil
    // 将大于目标值的链表的头节点接到小于目标值的链表的尾
    list1.Next = dummyNode2.Next
    // 返回小于目标值的链表的头节点
    return dummyNode1.Next
}

排序链表

148. 排序链表 - 力扣（LeetCode）

方法一：开辟额外空间存储节点值排序后重新分配节点值

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


func sortList(head *ListNode) *ListNode {
    nums := make([]int, 0)
    cur := head
    for cur != nil {
        nums = append(nums, cur.Val)
        cur = cur.Next
    }
    sort.Ints(nums)
    cur = head
    for i := 0; i < len(nums); i++ {
        cur.Val = nums[i]
        cur = cur.Next
    }
    return head
}

时间复杂度：$O(n)$
空间复杂度：$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


func sortList(head *ListNode) *ListNode {
    return mergeSort(head)
}

// 归并排序
func mergeSort(head *ListNode) *ListNode {
    // 无节点或只有一个节点
    if head == nil || head.Next == nil {
        return head
    }
    // 快慢指针法找中点
    slow, fast := head, head.Next
    // 快指针为空(奇)或next域为空(偶)时,慢指针指向中点
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    // 断开中间节点
    temp := slow.Next
    slow.Next = nil
    // 向左右递归
    left := mergeSort(head)
    right := mergeSort(temp)
    // 合并
    return merge(left, right)
}
func merge(list1, list2 *ListNode) *ListNode {
    dummyNode := new(ListNode)
    cur := dummyNode
    // 遍历两条链比较节点值,升序连接到新链,直到一条链结束
    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            cur.Next = list1
            list1 = list1.Next
        } else {
            cur.Next = list2
            list2 = list2.Next
        }
        cur = cur.Next
    }
    // 将剩余节点直接连接到新链尾
    if list1 == nil {
        cur.Next = list2
    } else {
        cur.Next = list1
    }
    return dummyNode.Next
}

时间复杂度：$O(nlogn)$
空间复杂度：$O(1)$

重排链表

143. 重排链表 - 力扣（LeetCode）

寻找链表中点 + 链表逆序 + 合并链表：

找到原链表的中点断开
将原链表的右半端反转
将两条链合并

 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


func reorderList(head *ListNode) {
    if head.Next == nil {
        return
    }
    // 找链表中点并断开
    slow, fast := head, head.Next
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    list2Head := slow.Next
    slow.Next = nil
    // 反转右半部分链表
    var pre *ListNode
    for list2Head != nil {
        temp := list2Head.Next
        list2Head.Next = pre
        pre = list2Head
        list2Head = temp
    }
    // 合并
    list1, list2 := head.Next, pre
    cur := head
    toggle := true
    for list1 != nil && list2 != nil {
        // 切换器为真用右半部分
        if toggle {
            cur.Next = list2
            cur = cur.Next
            list2 = list2.Next
        } else {
            cur.Next = list1
            cur = cur.Next
            list1 = list1.Next
        }
        toggle = !toggle
    }
    if list1 != nil {
        cur.Next = list1
    } else {
        cur.Next = list2
    }
    return
}

环形链表

141. 环形链表 - 力扣（LeetCode）

思路：快慢指针，快慢指针相同则有环，证明：如果有环每走一步快慢指针距离会减 1

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


func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }
    slow, fast := head, head.Next
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }
    return false
}

回文链表

234. 回文链表 - 力扣（LeetCode）

 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


func isPalindrome(head *ListNode) bool {
    // 找中点
    slow, fast := head, head.Next
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    // 中点断开
    list2 := slow.Next
    slow.Next = nil
    // 反转右半链表
    var pre *ListNode
    for list2 != nil {
        temp := list2.Next
        list2.Next = pre
        pre = list2
        list2 = temp
    }
    // 逐个对比俩链表节点
    for head != nil && pre != nil {
        if head.Val != pre.Val {
            return false
        }
        head = head.Next
        pre = pre.Next
    }
    return true
}

随机链表的复制

138. 随机链表的复制 - 力扣（LeetCode）

思路一：哈希表存储节点

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


func copyRandomList(head *Node) *Node {
    oldCur := head
    NewDummyNode := new(Node)
    NewPre := NewDummyNode
    mp := make(map[*Node]*Node)
    // 复制旧节点,保存旧节点与新节点的一一映射
    for oldCur != nil {
        newNode := &Node{Val: oldCur.Val, Next: oldCur.Next, Random: oldCur.Random}
        mp[oldCur] = newNode
        NewPre.Next = newNode
        NewPre = NewPre.Next
        oldCur = oldCur.Next
    }
    // 遍历新链表,用字典值替换Random域
    newCur := NewDummyNode.Next
    for newCur != nil {
        newCur.Random = mp[newCur.Random]
        newCur = newCur.Next
    }
    return NewDummyNode.Next
}

时间复杂度：$O(n)$
空间复杂度：$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


func copyRandomList(head *Node) *Node {
    if head == nil {
        return head
    }
    // 复制节点跟在旧节点后面, Random域置空
    cur := head
    for cur != nil {
        clone := &Node{Val: cur.Val, Next: cur.Next}
        cur.Next = clone
        cur = clone.Next
    }
    // 处理Random域：新节点random域 = 旧节点random域后的新节点
    cur = head
    for cur != nil {
        if cur.Random != nil {
            cur.Next.Random = cur.Random.Next
        }
        cur = cur.Next.Next
    }
    // 分离新旧节点
    cur = head
    cloneHead := head.Next
    for cur != nil && cur.Next != nil {
        temp := cur.Next
        cur.Next = cur.Next.Next
        cur = temp
    }
    return cloneHead
}

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