链表

链表是与数组相对应的基础数据结构。数组靠内存连续实现 O(1) 随机访问，而链表靠指针串联实现 O(1) 插入删除（在已知节点位置的前提下）。在 Go 中，链表没有语言层面的语法糖，完全靠结构体指针来构建，这反而能让我们更清晰地理解指针操作的本质。本篇将覆盖单链表、双链表、循环链表的实现，反转、找环、合并、找中点等经典算法，以及 Go 标准库 container/list 的用法，最后用 LeetCode 真题收尾。链表题是面试中考察指针操作能力的核心题型，务必熟练。

一、单链表实现

1. 节点定义

单链表的节点由「数据」和「指向下一个节点的指针」组成。在 Go 中用结构体指针表示：

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

// 辅助：用切片快速构建链表，方便测试
func buildList(vals []int) *ListNode {
	dummy := &ListNode{}
	cur := dummy
	for _, v := range vals {
		cur.Next = &ListNode{Val: v}
		cur = cur.Next
	}
	return dummy.Next
}

// 辅助：打印链表
func printList(head *ListNode) {
	for head != nil {
		fmt.Printf("%d -> ", head.Val)
		head = head.Next
	}
	fmt.Println("nil")
}

func main() {
	head := buildList([]int{1, 2, 3, 4, 5})
	printList(head)
}

技巧：dummy（哑节点）是链表题的常用工具。在头节点可能变化的情况下（如删除头、在头部插入），引入 dummy 可以避免单独处理头节点的特殊情况，让逻辑统一。

2. 插入、删除、查找

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

// 头插法：在链表头部插入
func insertHead(head *ListNode, val int) *ListNode {
	return &ListNode{Val: val, Next: head}
}

// 尾插法：在链表尾部插入
func insertTail(head *ListNode, val int) *ListNode {
	dummy := &ListNode{Next: head}
	cur := dummy
	for cur.Next != nil {
		cur = cur.Next
	}
	cur.Next = &ListNode{Val: val}
	return dummy.Next
}

// 在下标 idx 处插入（0 表示头部）
func insertAt(head *ListNode, idx, val int) *ListNode {
	dummy := &ListNode{Next: head}
	cur := dummy
	for i := 0; i < idx && cur.Next != nil; i++ {
		cur = cur.Next
	}
	node := &ListNode{Val: val}
	node.Next = cur.Next
	cur.Next = node
	return dummy.Next
}

// 删除第一个值为 val 的节点
func deleteValue(head *ListNode, val int) *ListNode {
	dummy := &ListNode{Next: head}
	cur := dummy
	for cur.Next != nil {
		if cur.Next.Val == val {
			cur.Next = cur.Next.Next
			break
		}
		cur = cur.Next
	}
	return dummy.Next
}

// 查找值是否存在于链表
func search(head *ListNode, val int) bool {
	for head != nil {
		if head.Val == val {
			return true
		}
		head = head.Next
	}
	return false
}

func printList(head *ListNode) {
	for head != nil {
		fmt.Printf("%d -> ", head.Val)
		head = head.Next
	}
	fmt.Println("nil")
}

func main() {
	head := (*ListNode)(nil)
	head = insertTail(head, 1)
	head = insertTail(head, 2)
	head = insertTail(head, 3)
	printList(head)

	head = insertHead(head, 0)
	printList(head)

	head = insertAt(head, 2, 99)
	printList(head)

	head = deleteValue(head, 99)
	printList(head)

	fmt.Println("查找 2:", search(head, 2))
	fmt.Println("查找 99:", search(head, 99))
}

复杂度：

头插 O(1)，尾插 O(n)（需遍历到尾部，除非维护尾指针）。
删除给定值 O(n)（需先查找）。
查找 O(n)。

二、双链表实现

双链表每个节点除了 Next 还有 Prev 指针，可以双向遍历，删除节点时无需知道前驱即可 O(1) 完成（前提是持有该节点指针）。

package main

import "fmt"

type DListNode struct {
	Val  int
	Prev *DListNode
	Next *DListNode
}

type DoublyLinkedList struct {
	Head *DListNode
	Tail *DListNode
}

// 尾部插入
func (dl *DoublyLinkedList) PushBack(val int) {
	node := &DListNode{Val: val}
	if dl.Tail == nil {
		dl.Head = node
		dl.Tail = node
		return
	}
	node.Prev = dl.Tail
	dl.Tail.Next = node
	dl.Tail = node
}

// 头部插入
func (dl *DoublyLinkedList) PushFront(val int) {
	node := &DListNode{Val: val}
	if dl.Head == nil {
		dl.Head = node
		dl.Tail = node
		return
	}
	node.Next = dl.Head
	dl.Head.Prev = node
	dl.Head = node
}

// 删除指定节点（O(1)，已知节点指针）
func (dl *DoublyLinkedList) Remove(node *DListNode) {
	if node.Prev != nil {
		node.Prev.Next = node.Next
	} else {
		dl.Head = node.Next
	}
	if node.Next != nil {
		node.Next.Prev = node.Prev
	} else {
		dl.Tail = node.Prev
	}
}

func (dl *DoublyLinkedList) PrintForward() {
	for cur := dl.Head; cur != nil; cur = cur.Next {
		fmt.Printf("%d -> ", cur.Val)
	}
	fmt.Println("nil")
}

func (dl *DoublyLinkedList) PrintBackward() {
	for cur := dl.Tail; cur != nil; cur = cur.Prev {
		fmt.Printf("%d -> ", cur.Val)
	}
	fmt.Println("nil")
}

func main() {
	dl := &DoublyLinkedList{}
	dl.PushBack(1)
	dl.PushBack(2)
	dl.PushBack(3)
	dl.PushFront(0)
	dl.PrintForward()  // 0 -> 1 -> 2 -> 3 -> nil
	dl.PrintBackward() // 3 -> 2 -> 1 -> 0 -> nil

	// 删除中间节点 1
	target := dl.Head.Next // 值为 1
	dl.Remove(target)
	dl.PrintForward()
}

双链表相比单链表的优势：双向遍历、O(1) 删除已知节点；代价是每个节点多一个指针，空间开销更大。

三、循环链表

循环链表的尾节点指向头节点，形成一个环。常用于轮询调度、约瑟夫环等问题。Go 标准库 container/ring 就是循环链表。

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

// 构建循环链表
func buildCircular(vals []int) *ListNode {
	if len(vals) == 0 {
		return nil
	}
	head := &ListNode{Val: vals[0]}
	cur := head
	for i := 1; i < len(vals); i++ {
		cur.Next = &ListNode{Val: vals[i]}
		cur = cur.Next
	}
	cur.Next = head // 尾指向头
	return head
}

// 约瑟夫环：n 个人围成一圈，从第 k 个开始数，数到 m 的出列
func josephus(n, k, m int) int {
	head := buildCircular(make([]int, 0))
	_ = head
	// 简化：直接用数学递推公式（逆推）
	// f(n,m) = (f(n-1,m) + m) % n, f(1,m)=0
 survivor := 0
	for i := 2; i <= n; i++ {
		survivor = (survivor + m) % i
	}
	return survivor + 1 // 编号从 1 开始
}

func main() {
	// 经典约瑟夫问题：n=5, m=3，最后剩下的是 4
	fmt.Println("约瑟夫 n=5 m=3 幸存者编号:", josephus(5, 1, 3))
}

四、常见链表算法

1. 反转链表（迭代 + 递归）

反转链表是面试最高频的链表题，必须两种写法都会。

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

// 迭代反转
func reverseList(head *ListNode) *ListNode {
	var prev *ListNode
	cur := head
	for cur != nil {
		next := cur.Next
		cur.Next = prev
		prev = cur
		cur = next
	}
	return prev
}

// 递归反转
func reverseListRecursive(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	newHead := reverseListRecursive(head.Next)
	head.Next.Next = head
	head.Next = nil
	return newHead
}

func buildList(vals []int) *ListNode {
	dummy := &ListNode{}
	cur := dummy
	for _, v := range vals {
		cur.Next = &ListNode{Val: v}
		cur = cur.Next
	}
	return dummy.Next
}

func printList(head *ListNode) {
	for head != nil {
		fmt.Printf("%d -> ", head.Val)
		head = head.Next
	}
	fmt.Println("nil")
}

func main() {
	head := buildList([]int{1, 2, 3, 4, 5})
	printList(reverseList(head))

	head2 := buildList([]int{1, 2, 3, 4, 5})
	printList(reverseListRecursive(head2))
}

2. 检测环（快慢指针）

Floyd 龟兔赛跑算法：快指针每次走两步，慢指针每次走一步，若有环必相遇。

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

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

func main() {
	// 构造带环链表：1->2->3->4->2
	n1 := &ListNode{Val: 1}
	n2 := &ListNode{Val: 2}
	n3 := &ListNode{Val: 3}
	n4 := &ListNode{Val: 4}
	n1.Next = n2
	n2.Next = n3
	n3.Next = n4
	n4.Next = n2 // 环
	fmt.Println("有环?", hasCycle(n1))
}

3. 找环入口

当快慢相遇后，把其中一个指针重置到 head，然后两指针都每次走一步，再次相遇点即为环入口。证明依赖于「相遇时 slow 走的距离 = a + b，fast 走了 a + b + n·环长」，化简后可得 a = (n-1)·环长 + (环长 - b)。

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

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 {
			// 相遇后，重置一个指针到 head
			slow = head
			for slow != fast {
				slow = slow.Next
				fast = fast.Next
			}
			return slow
		}
	}
	return nil
}

func main() {
	n1 := &ListNode{Val: 1}
	n2 := &ListNode{Val: 2}
	n3 := &ListNode{Val: 3}
	n4 := &ListNode{Val: 4}
	n1.Next = n2
	n2.Next = n3
	n3.Next = n4
	n4.Next = n2
	entry := detectCycle(n1)
	if entry != nil {
		fmt.Println("环入口值:", entry.Val) // 2
	}
}

4. 合并有序链表

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func mergeTwoLists(l1, l2 *ListNode) *ListNode {
	dummy := &ListNode{}
	cur := dummy
	for l1 != nil && l2 != nil {
		if l1.Val <= l2.Val {
			cur.Next = l1
			l1 = l1.Next
		} else {
			cur.Next = l2
			l2 = l2.Next
		}
		cur = cur.Next
	}
	if l1 != nil {
		cur.Next = l1
	} else {
		cur.Next = l2
	}
	return dummy.Next
}

func buildList(vals []int) *ListNode {
	dummy := &ListNode{}
	cur := dummy
	for _, v := range vals {
		cur.Next = &ListNode{Val: v}
		cur = cur.Next
	}
	return dummy.Next
}

func printList(head *ListNode) {
	for head != nil {
		fmt.Printf("%d -> ", head.Val)
		head = head.Next
	}
	fmt.Println("nil")
}

func main() {
	l1 := buildList([]int{1, 3, 5, 7})
	l2 := buildList([]int{2, 4, 6, 8})
	printList(mergeTwoLists(l1, l2))
}

5. 链表中点（快慢指针）

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

// 返回链表中点，节点数为偶数时返回前一个中点
func middleNode(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast.Next != nil && fast.Next.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}

func buildList(vals []int) *ListNode {
	dummy := &ListNode{}
	cur := dummy
	for _, v := range vals {
		cur.Next = &ListNode{Val: v}
		cur = cur.Next
	}
	return dummy.Next
}

func main() {
	head := buildList([]int{1, 2, 3, 4, 5})
	mid := middleNode(head)
	fmt.Println("中点值:", mid.Val) // 3
}

6. 删除倒数第 N 个节点

先用快慢指针让快指针先走 n 步，再同步走，慢指针就停在倒数第 n+1 个节点。

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	dummy := &ListNode{Next: head}
	fast, slow := dummy, dummy
	for i := 0; i < n; i++ {
		fast = fast.Next
	}
	for fast.Next != nil {
		fast = fast.Next
		slow = slow.Next
	}
	slow.Next = slow.Next.Next
	return dummy.Next
}

func buildList(vals []int) *ListNode {
	dummy := &ListNode{}
	cur := dummy
	for _, v := range vals {
		cur.Next = &ListNode{Val: v}
		cur = cur.Next
	}
	return dummy.Next
}

func printList(head *ListNode) {
	for head != nil {
		fmt.Printf("%d -> ", head.Val)
		head = head.Next
	}
	fmt.Println("nil")
}

func main() {
	head := buildList([]int{1, 2, 3, 4, 5})
	head = removeNthFromEnd(head, 2)
	printList(head) // 1 -> 2 -> 3 -> 5 -> nil
}

7. 两个链表的交点

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

// 浪漫解法：两个指针分别走 A+B 和 B+A，必在交点相遇
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	if headA == nil || headB == nil {
		return nil
	}
	pa, pb := headA, headB
	for pa != pb {
		if pa == nil {
			pa = headB
		} else {
			pa = pa.Next
		}
		if pb == nil {
			pb = headA
		} else {
			pb = pb.Next
		}
	}
	return pa
}

func main() {
	// 构造交点：公共节点
	common := &ListNode{Val: 8, Next: &ListNode{Val: 9}}
	a := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: common}}
	b := &ListNode{Val: 3, Next: common}
	inter := getIntersectionNode(a, b)
	if inter != nil {
		fmt.Println("交点值:", inter.Val) // 8
	}
}

五、Go 标准库中的链表：container/list

container/list 是 Go 标准库提供的双向链表实现，泛型版本（container/list 仍是非泛型，存 any）。

package main

import (
	"container/list"
	"fmt"
)

func main() {
	l := list.New()

	// 尾部插入
	l.PushBack(1)
	l.PushBack(2)
	l.PushBack(3)
	// 头部插入
	l.PushFront(0)

	// 遍历
	fmt.Print("正向: ")
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Printf("%v ", e.Value)
	}
	fmt.Println()

	fmt.Print("反向: ")
	for e := l.Back(); e != nil; e = e.Prev() {
		fmt.Printf("%v ", e.Value)
	}
	fmt.Println()

	// 删除指定元素
	elem := l.Front().Next() // 值为 1
	l.Remove(elem)

	fmt.Print("删除后: ")
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Printf("%v ", e.Value)
	}
	fmt.Println()

	fmt.Println("长度:", l.Len())
}

工程中除非确实频繁在中间插入删除，否则优先用切片。container/list 存 any 类型会带来装箱开销和类型不安全。

六、LeetCode 经典题解析

1. 反转链表 II（LC 92）

反转从位置 left 到 right 的子链表。

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseBetween(head *ListNode, left, right int) *ListNode {
	dummy := &ListNode{Next: head}
	// 找到 left 的前驱
	prev := dummy
	for i := 0; i < left-1; i++ {
		prev = prev.Next
	}
	// cur 是要反转的第一个节点
	cur := prev.Next
	// 头插法：把 cur.Next 插到 prev 后面
	for i := 0; i < right-left; i++ {
		next := cur.Next
		cur.Next = next.Next
		next.Next = prev.Next
		prev.Next = next
	}
	return dummy.Next
}

func buildList(vals []int) *ListNode {
	dummy := &ListNode{}
	cur := dummy
	for _, v := range vals {
		cur.Next = &ListNode{Val: v}
		cur = cur.Next
	}
	return dummy.Next
}

func printList(head *ListNode) {
	for head != nil {
		fmt.Printf("%d -> ", head.Val)
		head = head.Next
	}
	fmt.Println("nil")
}

func main() {
	head := buildList([]int{1, 2, 3, 4, 5})
	printList(reverseBetween(head, 2, 4)) // 1 -> 4 -> 3 -> 2 -> 5
}

2. K 个一组反转（LC 25）

每 k 个节点一组进行反转，不足 k 个保持原样。

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseKGroup(head *ListNode, k int) *ListNode {
	dummy := &ListNode{Next: head}
	prevGroup := dummy

	for {
		// 检查剩余是否够 k 个
		tail := prevGroup
		for i := 0; i < k; i++ {
			tail = tail.Next
			if tail == nil {
				return dummy.Next
			}
		}
		nextGroup := tail.Next
		// 反转 [prevGroup.Next, tail]
		prev, cur := nextGroup, prevGroup.Next
		for cur != nextGroup {
			tmp := cur.Next
			cur.Next = prev
			prev = cur
			cur = tmp
		}
		// 衔接
		newHead := tail
		newTail := prevGroup.Next
		prevGroup.Next = newHead
		newTail.Next = nextGroup
		prevGroup = newTail
	}
}

func buildList(vals []int) *ListNode {
	dummy := &ListNode{}
	cur := dummy
	for _, v := range vals {
		cur.Next = &ListNode{Val: v}
		cur = cur.Next
	}
	return dummy.Next
}

func printList(head *ListNode) {
	for head != nil {
		fmt.Printf("%d -> ", head.Val)
		head = head.Next
	}
	fmt.Println("nil")
}

func main() {
	head := buildList([]int{1, 2, 3, 4, 5})
	printList(reverseKGroup(head, 2)) // 2 -> 1 -> 4 -> 3 -> 5
}

3. 环形链表 II（LC 142）

前面已经实现了 detectCycle，这里不再重复，重点回顾证明思路：相遇后让一个指针回到 head 同步走，相遇点即为入口。

七、复杂度分析汇总

操作	单链表	双链表	备注
访问第 i 个	O(n)	O(n)	无法随机访问
头部插入/删除	O(1)	O(1)	链表优势
尾部插入	O(n) / O(1) 带尾指针	O(1) 带尾指针
中间插入（已知前驱）	O(1)	O(1)	数组为 O(n)
删除已知节点	O(n) 需找前驱	O(1)	双链表优势
查找	O(n)	O(n)

八、小结

链表是数据结构的「指针入门课」，本篇要点：

单链表节点由 Val 和 Next 组成，Go 中用结构体指针实现。dummy 哑节点能统一处理头节点变化的边界情况，是面试的标准工具。
双链表多了 Prev 指针，支持双向遍历和 O(1) 删除已知节点，代价是空间。Go 标准库 container/list 即双向链表。
循环链表尾指向头，适合轮询场景；约瑟夫问题有 O(n) 的数学递推解法。
反转链表迭代法用三指针（prev/cur/next），递归法核心是 head.Next.Next = head。
快慢指针是链表题的核心套路：找中点、检测环、找环入口、删除倒数第 N 个。
合并有序链表用 dummy + 双指针，是归并排序链表版的基础。
两链表交点的浪漫解法：两指针分别走 A+B、B+A，必在交点相遇。

链表题的难点不在于思路多复杂，而在于指针操作的细节容易写错。建议每写完一段都画图跟踪指针走向，特别是断开和重新连接的顺序。下一篇我们将学习栈与队列——它们都既可以用数组也可以用链表实现，是很多高级算法的基础工具。

入门篇

进阶篇

资深篇

链表

一、单链表实现

1. 节点定义

2. 插入、删除、查找

二、双链表实现

三、循环链表

四、常见链表算法

1. 反转链表（迭代 + 递归）

2. 检测环（快慢指针）

3. 找环入口

4. 合并有序链表

5. 链表中点（快慢指针）

6. 删除倒数第 N 个节点

7. 两个链表的交点

五、Go 标准库中的链表：container/list

六、LeetCode 经典题解析

1. 反转链表 II（LC 92）

2. K 个一组反转（LC 25）

3. 环形链表 II（LC 142）

七、复杂度分析汇总

八、小结

链表 ​

一、单链表实现 ​

1. 节点定义 ​

2. 插入、删除、查找 ​

二、双链表实现 ​

三、循环链表 ​

四、常见链表算法 ​

1. 反转链表（迭代 + 递归） ​

2. 检测环（快慢指针） ​

3. 找环入口 ​

4. 合并有序链表 ​

5. 链表中点（快慢指针） ​

6. 删除倒数第 N 个节点 ​

7. 两个链表的交点 ​

五、Go 标准库中的链表：container/list ​

六、LeetCode 经典题解析 ​

1. 反转链表 II（LC 92） ​

2. K 个一组反转（LC 25） ​

3. 环形链表 II（LC 142） ​

七、复杂度分析汇总 ​

八、小结 ​

链表

一、单链表实现

1. 节点定义

2. 插入、删除、查找

二、双链表实现

三、循环链表

四、常见链表算法

1. 反转链表（迭代 + 递归）

2. 检测环（快慢指针）

3. 找环入口

4. 合并有序链表

5. 链表中点（快慢指针）

6. 删除倒数第 N 个节点

7. 两个链表的交点

五、Go 标准库中的链表：container/list

六、LeetCode 经典题解析

1. 反转链表 II（LC 92）

2. K 个一组反转（LC 25）

3. 环形链表 II（LC 142）

七、复杂度分析汇总

八、小结