DAY 3

本篇部分题目在 『算法拾遗』链表（Linked List） 中已经做过

203.移除链表元素

还有一个递归版，但是那个空间复杂度是 O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
func removeElements(head *ListNode, val int) *ListNode {
    dummy := &ListNode{Next: head}
    curr := dummy
    for curr.Next != nil {
        if curr.Next.Val == val {
            curr.Next = curr.Next.Next
        } else {
            curr = curr.Next
        }
    }

    return dummy.Next
}

707.设计链表

分别写了单向链表和双向链表两个版本

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
70
71
72
73
74
type MyLinkedList struct {
    head *LinkNode
    size int
}

type LinkNode struct {
    val  int
    next *LinkNode
}

func Constructor() MyLinkedList {
    dummyHead := &LinkNode{}
    return MyLinkedList{
        head: dummyHead,
        size: 0,
    }
}

func (this *MyLinkedList) Get(index int) int {
    if index < 0 || index >= this.size {
        return -1
    }
    cur := this.head.next
    for i := 0; i < index; i++ {
        cur = cur.next
    }
    return cur.val
}

func (this *MyLinkedList) AddAtHead(val int) {
    newNode := &LinkNode{val: val}
    newNode.next = this.head.next
    this.head.next = newNode
    this.size++
}
func (this *MyLinkedList) AddAtTail(val int) {
    newNode := &LinkNode{val: val}
    cur := this.head
    for cur.next != nil {
        cur = cur.next
    }
    cur.next = newNode
    this.size++
}

func (this *MyLinkedList) AddAtIndex(index int, val int) {
    if index < 0 || index > this.size {
        return
    }
    if index == this.size {
        this.AddAtTail(val)
        return
    }
    cur := this.head
    for i := 0; i < index; i++ {
        cur = cur.next
    }
    newNode := &LinkNode{val: val}
    newNode.next = cur.next
    cur.next = newNode
    this.size++
}

func (this *MyLinkedList) DeleteAtIndex(index int) {
    if index < 0 || index >= this.size {
        return
    }
    cur := this.head
    for i := 0; i < index; i++ {
        cur = cur.next
    }
    cur.next = cur.next.next
    this.size--
}
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
type MyLinkedList struct {
    size int
    head *Node
    tail *Node
}

type Node struct {
    val        int
    next, prev *Node
}

func Constructor() MyLinkedList {
    dummy := &Node{}
    dummy.next = dummy
    dummy.prev = dummy

    return MyLinkedList{
        size: 0,
        head: dummy,
        tail: dummy,
    }
}

func (this *MyLinkedList) Get(index int) int {
    if index < 0 || index >= this.size {
        return -1
    }
    curr := this.head.next
    for i := 0; i < index; i++ {
        curr = curr.next
    }
    return curr.val
}

func (this *MyLinkedList) AddAtHead(val int) {
    newNode := &Node{
        val:  val,
        next: this.head.next,
        prev: this.head,
    }
    this.head.next.prev = newNode
    this.head.next = newNode
    this.size++
}

func (this *MyLinkedList) AddAtTail(val int) {
    newNode := &Node{
        val:  val,
        next: this.tail,
        prev: this.tail.prev,
    }
    this.tail.prev.next = newNode
    this.tail.prev = newNode
    this.size++
}

func (this *MyLinkedList) AddAtIndex(index int, val int) {
    if index < 0 || index > this.size {
        return
    }
    curr := this.head.next
    for index != 0 {
        curr = curr.next
        index--
    }
    newNode := &Node{
        val:  val,
        prev: curr.prev,
        next: curr,
    }
    curr.prev.next = newNode
    curr.prev = newNode
    this.size++
}

func (this *MyLinkedList) DeleteAtIndex(index int) {
    if index < 0 || index >= this.size {
        return
    }
    curr := this.head.next
    for index != 0 {
        curr = curr.next
        index--
    }
    curr.next.prev = curr.prev
    curr.prev.next = curr.next
    this.size--
}

206.反转链表

经典反转链表，操作过程如下

  1. 初始化当前节点为头节点
  2. 暂存下一个节点
  3. 将当前节点指向前一个节点
  4. 前驱节点后移
  5. 当前节点后移
  6. 重复 1-4，只到当前节点为 NULL ，输出前驱结点为新的头结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func reverseList(head *ListNode) *ListNode {
	// 定义前驱节点、当前节点、后继节点
	var prev *ListNode = nil
	var next *ListNode = nil
	var curr *ListNode = head

	// 遍历链表
	for curr != nil {
		// 保存下一个节点
		next = curr.Next
		// 当前节点指向前驱节点
		curr.Next = prev
		// 前驱节点后移
		prev = curr
		// 当前节点后移
		curr = next
	}

	// 返回前驱节点
	return prev
}

我一开始也不是很懂，所以我画了个图一步一步来，图画出来我就懂了

image-20230601下午103709377

类似地，还有一个递归的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func reverseList(head *ListNode) *ListNode {
	// 如果链表为空或者只有一个节点，直接返回原链表
	if head == nil || head.Next == nil {
		return head
	}
	// 递归反转除头节点外的子链表
	p := reverseList(head.Next)
	// 将当前节点的下一个节点指向当前节点，实现反转
	head.Next.Next = head
	// 将当前节点的下一个节点置空，断开原链表中的连接
	head.Next = nil
	// 返回反转后的链表的头节点
	return p
}

DAY 4

本篇部分题目在 『算法拾遗』链表（Linked List） 中已经做过

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func swapPairs(head *ListNode) *ListNode {
    dummy:=&ListNode{
        Next: head,
    }

    curr := dummy

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

        first.Next=second.Next
        second.Next=first
        curr.Next=second

        curr=curr.Next.Next
    }

    return dummy.Next
}

19. 删除链表的倒数第 N 个结点

经典快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{
        Next: head,
    }
    fast, slow := dummy, dummy

    for i := 1; i < n; i++ {
        fast = fast.Next
    }

    for fast.Next.Next != nil {
        fast = fast.Next
        slow = slow.Next
    }

    slow.Next = slow.Next.Next

    return dummy.Next
}

面试题02.07.链表相交

双指针，先对齐再往后走

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 getIntersectionNode(headA, headB *ListNode) *ListNode {
    lenA, lenB := 0, 0

    for curr := headA; curr != nil; curr = curr.Next {
        lenA++
    }
    for curr := headB; curr != nil; curr = curr.Next {
        lenB++
    }

    if lenA < lenB {
        headA, headB = headB, headA
        lenA, lenB = lenB, lenA
    }

    diff := lenA - lenB

    a, b := headA, headB
    for i := 0; i < diff; i++ {
        a = a.Next
    }

    for a != nil && b != nil {
        if a == b {
            return a
        }
        a = a.Next
        b = b.Next
    }
    return nil
}

142.环形链表 II

快慢指针找环，然后让其中一个回到原点，再同步前进

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 detectCycle(head *ListNode) *ListNode {
    dummy := &ListNode{
        Next: head,
    }

    fast, slow := dummy, dummy

    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next

        if fast == slow {
            break
        }
    }

    if fast == nil || fast.Next == nil {
        return nil
    }

    fast = dummy

    for fast != slow {
        fast = fast.Next
        slow = slow.Next
    }

    return fast

}

DAY 5

周日休息