Famousmai's blog
famousmai
2023-02-18
目录

链表

# 反转链表 (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
}
1
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

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

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

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

# 链表的中间结点 (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
}
1
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

}
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

# 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

}
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

# 删除排序链表中的重复元素 (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

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

  • 算法思路：

    1. 找中点：通过双指针技巧的快慢指针

    2. 奇数偶数判断：fast 指针没有指向 null，说明链表长度为奇数，slow 还要再前进一步

    3. 反转链表：从 slow 开始反转后面的链表

    4. 开始比较

  • 时间复杂度 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
}
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
编辑 (opens new window)
#算法#快慢指针
上次更新: 2023/03/03, 15:50:07
数组
字符串

← 字符串→

最近更新
01
策略模式
03-13
02
单例模式
03-05
03
设计模式介绍
03-05
更多文章>
Theme by Vdoing | Copyright © 2022-2023 Evan Xu | MIT License