数据结构与算法-链表

链表经典题目

25. K 个一组翻转链表 ❤️



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



func reverseKGroup(head *ListNode, k int) *ListNode {
	if head == nil || k == 1 {
		return head
	}
	tail := head
	for i := 0; i < k; i++ {
		if tail == nil {
			return head
		}
		tail = tail.Next
	}
	newHead := reverse(head, tail)
	head.Next = reverseKGroup(tail, k)
	return newHead
}

func reverse(head *ListNode, tail *ListNode) *ListNode {
	var pre *ListNode
	cur := head
	for cur != tail {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
	return pre
}





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 reverseKGroup(head *ListNode, k int) *ListNode {
	// 计算链表长度
	length := 0
	cur := head
	for cur != nil {
		length++
		cur = cur.Next
	}
	dummy := &ListNode{Next: head}
	preGroupEnd := dummy

	for length >= k {
		cur := preGroupEnd.Next
		nextGroupStart := cur

		var pre *ListNode
		for i := 0; i < k; i++ {
			next := cur.Next
			cur.Next = pre
			pre = cur
			cur = next
		}

		preGroupEnd.Next = pre
		nextGroupStart.Next = cur

		preGroupEnd = nextGroupStart
		length = length - k
	}

	return dummy.Next
}

92. 反转链表 II 



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



func reverseBetween(head *ListNode, left int, right int) *ListNode {
	if head == nil || head.Next == nil || left == right {
		return head
	}
	dummy := &ListNode{Next: head}
	slow := dummy
	for i := 1; i < left; i++ {
		slow = slow.Next
	}
	cur := slow.Next
	var pre *ListNode
	for i := left; i <= right; i++ {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
	slow.Next.Next = cur
	slow.Next = pre
	return dummy.Next
}

23. 合并 K 个升序链表 



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



func mergeKLists(lists []*ListNode) *ListNode {
	if len(lists) == 0 {
		return nil
	} else if len(lists) == 1 {
		return lists[0]
	}
	mid := len(lists) / 2
	l1 := mergeKLists(lists[:mid])
	l2 := mergeKLists(lists[mid:])
	return mergeTwoLists(l1, l2)
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	} else if l2 == nil {
		return l1
	}
	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
}





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



// 合并 K 个升序链表
func mergeKLists(lists []*ListNode) *ListNode {
	if len(lists) == 0 {
		return nil
	}

	// 从第一个链表开始
	mergedList := lists[0]

	// 依次合并每个链表
	for i := 1; i < len(lists); i++ {
		mergedList = mergeTwoLists(mergedList, lists[i])
	}

	return mergedList
}

// 合并两个有序链表
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
}

143. 重排链表 ❤️



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



func reorderList(head *ListNode) {
	if head == nil || head.Next == nil {
		return
	}

	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}

	var pre *ListNode
	cur := slow.Next
	for cur != nil {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}

	slow.Next = nil
	p1, p2 := head, pre
	for p2 != nil {
		next1, next2 := p1.Next, p2.Next
		p1.Next = p2
		p2.Next = next1
		p1 = next1
		p2 = next2
	}
}

160. 相交链表 



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



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





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 getIntersectionNode(headA, headB *ListNode) *ListNode {
	// 计算链表 A 的长度
	lengthA := 0
	for cur := headA; cur != nil; cur = cur.Next {
		lengthA++
	}

	// 计算链表 B 的长度
	lengthB := 0
	for cur := headB; cur != nil; cur = cur.Next {
		lengthB++
	}

	a, b := headA, headB
	// 让较长的链表先走几步
	for lengthA > lengthB {
		a = a.Next
		lengthA--
	}
	for lengthB > lengthA {
		b = b.Next
		lengthB--
	}

	// 同时遍历两个链表，找到相交节点
	for a != b {
		a = a.Next
		b = b.Next
	}

	return a
}

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



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



func deleteDuplicates(head *ListNode) *ListNode {
	dummy := &ListNode{Next: head}
	pre, cur := dummy, head
	for cur != nil {
		isDuplicate := false
		for cur.Next != nil && cur.Next.Val == cur.Val {
			cur = cur.Next
			isDuplicate = true
		}
		if isDuplicate {
			pre.Next = cur.Next
		} else {
			pre = cur
		}
		cur = cur.Next
	}
	return dummy.Next
}

148. 排序链表 



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 {
	if head == nil || head.Next == nil {
		return head
	}
	dummy := &ListNode{}
	dummy.Next = head

	slow, fast := dummy, dummy
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}

	rightHead := slow.Next
	slow.Next = nil

	l1 := sortList(head)
	l2 := sortList(rightHead)
	return mergeTwoLists(l1, l2)
}

func mergeTwoLists(l1, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	} else if l2 == nil {
		return l1
	}
	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 if l2 != nil {
		cur.Next = l2
	}

	return dummy.Next
}

234. 回文链表 



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



func isPalindrome(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return true
	}

	// 使用快慢指针找到链表的中间节点
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}

	// 反转链表的后半部分
	var pre *ListNode
	cur := slow
	for cur != nil {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}

	// 比较链表的前半部分和反转后的后半部分是否相同
	left, right := head, pre
	for right != nil {
		if left.Val != right.Val {
			return false
		}
		left = left.Next
		right = right.Next
	}

	return true
}

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



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



func deleteDuplicates(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	cur := head
	for cur.Next != nil {
		if cur.Next.Val == cur.Val {
			cur.Next = cur.Next.Next
		} else {
			cur = cur.Next
		}
	}

	return head
}

24. 两两交换链表中的节点 ❤️



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



func swapPairs(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	first := head
	second := head.Next

	first.Next = swapPairs(second.Next)
	second.Next = first

	return second
}





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



func swapPairs(head *ListNode) *ListNode {
	dummy := &ListNode{Next: head}
	pre := dummy

	for pre.Next != nil && pre.Next.Next != nil {
		first := pre.Next
		second := pre.Next.Next

		first.Next = second.Next
		second.Next = first
		pre.Next = second

		pre = first
	}

	return dummy.Next
}





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



func swapPairs(head *ListNode) *ListNode {
	dummy := &ListNode{Next: head}
	pre := dummy
	cur := head

	for cur != nil && cur.Next != nil {
		first := cur
		second := cur.Next

		first.Next = second.Next
		second.Next = first
		pre.Next = second

		pre = first
		cur = first.Next
	}

	return dummy.Next
}

138. 随机链表的复制 



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



func copyRandomList(head *Node) *Node {
	if head == nil {
		return nil
	}

	// 第一步：在每个节点后面插入一个新节点
	cur := head
	for cur != nil {
		newNode := &Node{Val: cur.Val, Next: cur.Next}
		cur.Next = newNode
		cur = newNode.Next
	}

	// 第二步：更新新节点的随机指针
	cur = head
	for cur != nil {
		if cur.Random != nil {
			cur.Next.Random = cur.Random.Next
		}
		cur = cur.Next.Next
	}

	// 第三步：拆分链表
	cur = head
	newHead := head.Next
	for cur != nil {
		newNode := cur.Next
		cur.Next = newNode.Next
		if newNode.Next != nil {
			newNode.Next = newNode.Next.Next
		}
		cur = cur.Next
	}

	return newHead
}

61. 旋转链表 



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 rotateRight(head *ListNode, k int) *ListNode {
	if head == nil || head.Next == nil || k == 0 {
		return head
	}

	length := 1
	cur := head
	for cur.Next != nil {
		length++
		cur = cur.Next
	}

	k = k % length
	if k == 0 {
		return head
	}

	cur.Next = head

	for i := 0; i < length-k; i++ {
		cur = cur.Next
	}

	newHead := cur.Next
	cur.Next = nil

	return newHead
}

补充题 1. 排序奇升偶降链表

image-20250416173609218



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



// 排序奇升偶降链表
func sortOddEvenList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
       return head
    }

    // 拆分奇偶链表
    odd, even := head, head.Next
    oddHead, evenHead := odd, even
    for even != nil && even.Next != nil {
       odd.Next = odd.Next.Next
       odd = odd.Next

       even.Next = even.Next.Next
       even = even.Next
    }
    odd.Next = nil // 非常重要

    // 反转偶数链表
    var pre *ListNode
    cur := evenHead
    for cur != nil {
       next := cur.Next
       cur.Next = pre
       pre = cur
       cur = next
    }
    evenHead = pre

    // 合并两个链表
    dummy := &ListNode{}
    cur = dummy
    l1, l2 := oddHead, evenHead
    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 if l2 != nil {
       cur.Next = l2
    }
    return dummy.Next
}

86. 分隔链表 



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 partition(head *ListNode, x int) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	leftHead := &ListNode{}
	rightHead := &ListNode{}

	left := leftHead
	right := rightHead

	cur := head
	for cur != nil {
		if cur.Val < x {
			left.Next = cur
			left = left.Next
		} else {
			right.Next = cur
			right = right.Next
		}
		cur = cur.Next
	}

	right.Next = nil // 特别注意：此处一定要断开，防止循环引用。
	left.Next = rightHead.Next

	return leftHead.Next
}

109. 有序链表转换二叉搜索树 



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



func findMiddle(head *ListNode) *ListNode {
	var pre *ListNode
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		pre = slow
		slow = slow.Next
		fast = fast.Next.Next
	}
	if pre != nil {
		pre.Next = nil // 切断链表
	}
	return slow
}

func sortedListToBST(head *ListNode) *TreeNode {
	if head == nil {
		return nil
	}
	mid := findMiddle(head)
	root := &TreeNode{Val: mid.Val}
	if head == mid {
		return root
	}
	root.Left = sortedListToBST(head)
	root.Right = sortedListToBST(mid.Next)
	return root
}

1171. 从链表中删去总和值为零的连续节点 



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



func removeZeroSumSublists(head *ListNode) *ListNode {
	dummy := &ListNode{Next: head}
	prefixSum := 0
	sumMap := make(map[int]*ListNode)
	sumMap[0] = dummy

	// 第一次遍历，记录前缀和及其对应的节点
	for cur := dummy; cur != nil; cur = cur.Next {
		prefixSum += cur.Val
		sumMap[prefixSum] = cur
	}

	// 第二次遍历，删除前缀和相同的节点之间的节点
	prefixSum = 0
	for cur := dummy; cur != nil; cur = cur.Next {
		prefixSum += cur.Val
		cur.Next = sumMap[prefixSum].Next
	}

	return dummy.Next
}

147. 对链表进行插入排序 



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



func insertionSortList(head *ListNode) *ListNode {
	dummy := &ListNode{}
	cur := head

	for cur != nil {
		// 保存下一个节点
		next := cur.Next
		// 找到插入位置
		pre := dummy
		for pre.Next != nil && pre.Next.Val < cur.Val {
			pre = pre.Next
		}
		// 插入节点
		cur.Next = pre.Next
		pre.Next = cur
		// 处理下一个节点
		cur = next
	}
	return dummy.Next
}

369. 给单链表加一

image-20220918214816966



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



func plusOne(head *ListNode) *ListNode {
	var stack []int

	for head != nil {
		stack = append(stack, head.Val)
		head = head.Next
	}

	carry := 1
	var pre *ListNode

	// 依次从栈顶取出节点值进行加一
	for len(stack) > 0 || carry > 0 {
		sum := carry
		if len(stack) > 0 {
			sum += stack[len(stack)-1]
			stack = stack[:len(stack)-1]
		}

		// 处理进位
		carry = sum / 10
		sum = sum % 10

		// 创建新节点并插入到链表头部
		cur := &ListNode{Val: sum}
		cur.Next = pre
		pre = cur
	}

	return pre
}

1669. 合并两个链表 



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



func mergeInBetween(list1 *ListNode, a int, b int, list2 *ListNode) *ListNode {
	dummy := &ListNode{Next: list1}
	preA := dummy
	preB := dummy
	for i := 0; i < a; i++ {
		preA = preA.Next
	}

	for i := 0; i < b+2; i++ {
		preB = preB.Next
	}

	preA.Next = list2
	tail := list2
	for tail.Next != nil {
		tail = tail.Next
	}

	tail.Next = preB

	return list1
}

面试题 02.01. 移除重复节点 



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



func removeDuplicateNodes(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	seem := make(map[int]bool)
	dummy := &ListNode{Next: head}
	pre := dummy
	cur := head
	for cur != nil {
		if seem[cur.Val] {
			pre.Next = cur.Next
		} else {
			pre = cur
		}
		seem[cur.Val] = true
		cur = cur.Next
	}

	return dummy.Next
}

1367. 二叉树中的链表 



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



func isSubPath(head *ListNode, root *TreeNode) bool {
	var dfs func(node *TreeNode, curr *ListNode) bool
	dfs = func(node *TreeNode, curr *ListNode) bool {
		if curr == nil {
			return true // 链表遍历完，返回 true
		}
		if node == nil || node.Val != curr.Val {
			return false // 当前节点为空或值不匹配，返回 false
		}
		// 继续遍历左右子树
		return dfs(node.Left, curr.Next) || dfs(node.Right, curr.Next)
	}

	// 从根节点开始遍历
	if root == nil {
		return false
	}
	return dfs(root, head) || isSubPath(head, root.Left) || isSubPath(head, root.Right)
}

1019. 链表中的下一个更大节点 



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



func nextLargerNodes(head *ListNode) []int {
	var nums []int
	cur := head
	for cur != nil {
		nums = append(nums, cur.Val)
		cur = cur.Next
	}

	res := make([]int, len(nums))
	var stack []int

	for i, num := range nums {
		for len(stack) > 0 && num > nums[stack[len(stack)-1]] {
			res[stack[len(stack)-1]] = num
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, i)
	}

	return res
}

725. 分隔链表 



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



func splitListToParts(head *ListNode, k int) []*ListNode {
	// 计算链表的长度
	length := 0
	for cur := head; cur != nil; cur = cur.Next {
		length++
	}

	// 计算每个部分的基本长度和额外节点数
	partSize := length / k
	extraSize := length % k

	// 创建结果数组
	res := make([]*ListNode, k)
	cur := head

	for i := 0; i < k; i++ {
		res[i] = cur
		// 计算当前部分的长度
		size := partSize
		if i < extraSize {
			size++ // 前面部分多一个节点
		}

		// 遍历当前部分
		for j := 0; j < size && cur != nil; j++ {
			if j == size-1 {
				next := cur.Next
				cur.Next = nil // 断开链表
				cur = next
			} else {
				cur = cur.Next
			}
		}
	}

	return res
}

146. LRU 缓存 



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



type Node struct {
	key, value int
	pre, next  *Node
}

type LRUCache struct {
	capacity   int
	cache      map[int]*Node
	head, tail *Node
}

func Constructor(capacity int) LRUCache {
	head := &Node{}
	tail := &Node{}
	head.next = tail
	tail.pre = head
	return LRUCache{
		capacity: capacity,
		cache:    make(map[int]*Node),
		head:     head,
		tail:     tail,
	}
}

func (this *LRUCache) Get(key int) int {
	if node, exists := this.cache[key]; exists {
		this.moveToHead(node)
		return node.value
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	if node, exists := this.cache[key]; exists {
		node.value = value
		this.moveToHead(node)
	} else {
		newNode := &Node{key: key, value: value}
		this.cache[key] = newNode
		this.addToHead(newNode)
		if len(this.cache) > this.capacity {
			removed := this.removeTail()
			delete(this.cache, removed.key)
		}
	}
}

func (this *LRUCache) moveToHead(node *Node) {
	this.removeNode(node)
	this.addToHead(node)
}

func (this *LRUCache) addToHead(node *Node) {
	node.pre = this.head
	node.next = this.head.next
	this.head.next.pre = node
	this.head.next = node
}

func (this *LRUCache) removeNode(node *Node) {
	node.pre.next = node.next
	node.next.pre = node.pre
}

func (this *LRUCache) removeTail() *Node {
	node := this.tail.pre
	this.removeNode(node)
	return node
}
本文作者:
本文链接: https://hgnulb.github.io/blog/2022/93052001
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！