环形链表#

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil {
        slow = slow.Next
        if fast.Next == nil {
            return nil
        }
        fast = fast.Next.Next
        if fast == slow {
            p := head
            for p != slow {
                p = p.Next
                slow = slow.Next
            }
            return p
        }
    }
    return nil
}

当 快慢指针相遇时是相遇点，如果想要找到初始环形点

就 重新定义一个指针 开始跑

两者相遇就是起始点

不要问为什么： 这个数学归纳法可以做，当作结论记一下所以我才写一篇博客记录

Gpt：

  1. 快慢指针相遇：首先使用快慢指针（fast和slow）来检测链表中是否存在环。快指针fast每次移动两步，慢指针slow每次移动一步。如果链表中有环，那么快指针最终会追上慢指针，即fast和slow会在环内的某个节点相遇。
  2. 寻找环的起始节点：一旦快慢指针相遇，我们需要找到环的起始节点。此时，代码中创建了一个新的指针p，它被初始化为链表的头节点head。
  3. 指针同步移动：然后，代码进入一个循环，在这个循环中，p和slow指针同步移动，每次移动一步，直到p和slow相遇。由于slow指针已经位于环内，所以当p和slow相遇时，p指针将指向环的起始节点。
  4. 返回结果：循环结束后，p指针指向的就是环的起始节点，然后返回这个节点。

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点

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

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

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

	slow.Next = slow.Next.Next

	return dummyHead.Next
}

好好领悟一下这个快慢指针的意义

LRU缓存#

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

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
type entry struct {
	key, value int
}

type LRUCache struct {
	capacity int
	list     *list.List
	cache    map[int]*list.Element
}

func Constructor(capacity int) LRUCache {
	return LRUCache{capacity, list.New(), map[int]*list.Element{}}
}

func (l *LRUCache) Get(key int) int {
	if elem, ok := l.cache[key]; ok {
		l.list.MoveToFront(elem)
		return elem.Value.(entry).value
	}
	return -1
}

func (l *LRUCache) Put(key, value int) {
	if elem, ok := l.cache[key]; ok {
		// Update the value and move it to the front
		elem.Value = entry{key, value}
		l.list.MoveToFront(elem)
		return
	}

	if l.list.Len() >= l.capacity {
		// Remove the least recently used item
		lru := l.list.Back()
		if lru != nil {
			delete(l.cache, lru.Value.(entry).key)
			l.list.Remove(lru)
		}
	}

	// Add the new item to the front
	elem := l.list.PushFront(entry{key, value})
	l.cache[key] = elem
}