链表
# 反转链表 (opens new window)
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
其他重复题目
# 迭代法
时间复杂度:O(N)、空间复杂度: O(1)
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
current := head
for current != nil {
next := current.Next
current.Next = prev
prev = current
current = next
}
return prev
}
2
3
4
5
6
7
8
9
10
11
12
# 递归法
时间复杂度:O(N) 、空间复杂度:O(N)
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
last := reverseList(head.Next)
head.Next.Next = head
head.Next = nil
return last
}
2
3
4
5
6
7
8
9
10
11
12
13
# 环形链表 (opens new window)
给你一个链表的头节点 head ,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 ,则返回 true 。 否则,返回 false 。
# 哈希
func hasCycle(head *ListNode) bool {
hashMap := map[*ListNode]struct{}{}
for head != nil {
if _,ok := hashMap[head] ; ok {
return true
}
hashMap[head] = struct{}{}
head = head.Next
}
return false
}
2
3
4
5
6
7
8
9
10
11
12
13
# 快慢指针
func hasCycle(head *ListNode) bool {
slow := head
fast := head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
return true
}
}
return false
}
2
3
4
5
6
7
8
9
10
11
12
# 合并两个有序链表 (opens new window)
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
dummyHead := &ListNode{}
head := dummyHead
for list1 != nil && list2 != nil {
if list1.Val < list2.Val {
head.Next = list1
list1 = list1.Next
} else {
head.Next = list2
list2 = list2.Next
}
head = head.Next
}
if list1 != nil {
head.Next = list1
}
if list2 != nil {
head.Next = list2
}
return dummyHead.Next
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 剑指 Offer 22. 链表中倒数第k个节点 (opens new window)
输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。 例如,一个链表有 6 个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
func getKthFromEnd(head *ListNode, k int) *ListNode {
p1 := head
for i := 1;i <= k; i++ {// p1 先走 k 步
p1 = p1.Next
}
p2 := head
for p1 != nil{ // 当 p1 走完,p2 指向的就是 n-k 的位置
p1 = p1.Next
p2 = p2.Next
}
return p2
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 删除链表的倒数第 N 个结点 (opens new window)
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
func removeNthFromEnd(head *ListNode, n int) *ListNode {
dummyHead := &ListNode{}
p := dummyHead
p.Next = head
x := findEnd(p, n + 1)
x.Next = x.Next.Next
return p.Next
}
func getKthFromEnd(head *ListNode, k int) *ListNode {
p1 := head
for i := 1; i <= k; i++ {
p1 = p1.Next
}
p2 := head
for p1 != nil {
p1 = p1.Next
p2 = p2.Next
}
return p2
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 分隔链表 (opens new window)
给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你应当 保留 两个分区中每个节点的初始相对位置。
func partition(head *ListNode, x int) *ListNode {
dump1 := &ListNode{}
dump2 := &ListNode{}
p1 := dump1
p2 := dump2
p := head
for p != nil {
if p.Val < x {
p1.Next = p
p1 = p1.Next
}else {
p2.Next = p
p2 = p2.Next
}
// 断开原链中每个节点的next
temp := p.Next
p.Next = nil
p = temp
}
// 连接两条链
p1.Next = dump2.Next
return dump1.Next
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 链表的中间结点 (opens new window)
给定一个头结点为 head 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。
func middleNode(head *ListNode) *ListNode {
slow := head
fast := head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
2
3
4
5
6
7
8
9
# 剑指 Offer II 022. 链表中环的入口节点 (opens new window)
给定一个链表,返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环,则返回 null。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意,pos 仅仅是用于标识环的情况,并不会作为参数传递到函数中。 说明:不允许修改给定的链表。
func detectCycle(head *ListNode) *ListNode {
slow := head
fast := head
// 先找出环的相遇点
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
break
}
}
// 快指针为空,说明没有环
if fast == nil || fast.Next == nil{
return nil
}
// 快慢任意一个指针重新指向head
slow = head
// 同步前进,再次相遇的点,即是环的起点
for slow != fast {
slow = slow.Next
fast = fast.Next
}
return slow
}
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
# K 个一组翻转链表 (opens new window)
给你链表的头节点 head ,每 k 个节点一组进行翻转,请你返回修改后的链表。 k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。 你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。
func reverseKGroup(head *ListNode, k int) *ListNode {
if head == nil {
return head
}
a := head
b := head
// 小于k的则不改变链表的顺序,直接返回
for i := 0; i < k; i++ {
if b == nil {
return head
}
b = b.Next
}
newHead := reverse(a, b)
a.Next = reverseKGroup(b, k)
return newHead
}
// 反转a到b之间的链表,[a,b) 左闭右开
func reverse(a *ListNode, b *ListNode) *ListNode {
var pre *ListNode
curr := a
nxt := a
for curr != b {
nxt = curr.Next
curr.Next = pre
pre = curr
curr = nxt
}
return pre
}
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
# 删除排序链表中的重复元素 (opens new window)
给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil {
return head
}
slow := head
fast := head
for fast != nil {
if slow.Val != fast.Val {
slow.Next = fast
slow = slow.Next
}
fast = fast.Next
}
// 断开后面的重复的连接
slow.Next = nil
return head
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 回文链表 (opens new window)
给你一个单链表的头节点
head
,请你判断该链表是否为回文链表。如果是,返回true
;否则,返回false
。
算法思路:
找中点:通过双指针技巧的快慢指针
奇数偶数判断:fast 指针没有指向 null,说明链表长度为奇数,slow 还要再前进一步
反转链表:从 slow 开始反转后面的链表
开始比较
时间复杂度 O(N),空间复杂度 O(1)
func isPalindrome(head *ListNode) bool {
if head == nil {
return false
}
slow := head
fast := head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
// fast 没指向空,说明是链表是奇数,slow要多走一步
if fast != nil {
slow = slow.Next
}
left := head
right := reverse(slow) // 反转slow后的节点,得到右节点
for right != nil { // todo 注意这里不能用左节点循环
if left.Val != right.Val{
return false
}
left = left.Next
right = right.Next
}
return true
}
// 反转链表
func reverse(head *ListNode) *ListNode{
curr := head
var prev *ListNode
for curr != nil {
nex := curr.Next
curr.Next = prev
prev = curr
curr = nex
}
return prev
}
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