数据结构与算法-链表

链表经典题目

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
}

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

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

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
	}
	if l1.Val < l2.Val {
		l1.Next = mergeTwoLists(l1.Next, l2)
		return l1
	} else {
		l2.Next = mergeTwoLists(l1, l2.Next)
		return l2
	}
}

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
}

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

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

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

147. 对链表进行插入排序

1

write your code here

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

func sortList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	slow, fast := head, head
	var pre *ListNode
	for fast != nil && fast.Next != nil {
		pre = slow
		slow = slow.Next
		fast = fast.Next.Next
	}
	pre.Next = nil

	l1 := sortList(head)
	l2 := sortList(slow)
	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
}

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

1

write your code here

725. 分隔链表

1

write your code here

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

1

write your code here

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

func rotateRight(head *ListNode, k int) *ListNode {
	if head == nil || head.Next == nil || k == 0 {
		return head
	}

	// 计算链表长度并找到尾节点
	cur := head
	count := 1
	for cur.Next != nil {
		count++
		cur = cur.Next
	}
	cur.Next = head // 形成循环链表
	k = k % count   // 实际需要移动的步数

	// 找到新的头部和尾部
	for i := 0; i < count-k; i++ {
		cur = cur.Next
	}

	newHead := cur.Next
	cur.Next = nil

	return newHead
}

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

1

write your code here

高频面试题-排序奇升偶降链表

1

write your code here

369. 给单链表加一

image-20220918214816966

1

write your code here

146. LRU 缓存

1

write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2022/93052001
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！