1.相交链表#
题目描述：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交**：**
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0listA - 第一个链表listB - 第二个链表skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
示例 1：
1
2
3
4
5
6
| 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。
|
示例 2：
1
2
3
4
5
| 输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
|
示例 3：
1
2
3
4
5
| 输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：No intersection
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
|
题解：挺有意思的，这样不停循环总有一次会交汇的#
1
2
3
4
5
6
7
8
| class Solution(object):
def getIntersectionNode(self, headA, headB):
pa = headA
pb = headB
while pa != pb:
pa = pa.next if pa else headB
pb = pb.next if pb else headA
return pa
|
2.反转链表#
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
1
2
| 输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
|
示例 2：
1
2
| 输入：head = [1,2]
输出：[2,1]
|
示例 3：
题解:可以说是经典解法了#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| # Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
pre=None
cur = head
while cur:
next_node = cur.next
cur.next = pre
pre = cur
cur = next_node
return pre
|
3.回文链表#
题目描述#
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false
题解：方法都是转化成value判断，看谁写的效率高罢了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| # Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
values = []
cur = head
cnt = 0
while cur:
values.append(cur.val)
cur = cur.next
cnt += 1
for i in range((int)(cnt/2)):
if values[i] != values[cnt-i-1]:
return False
return True
|
4.环形链表#
题目描述#
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
1.快慢指针法：顾名思义，我懒得解释
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| # Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
|
2.嗨嗨嗨，我用集合想不到吧set来了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| # Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
cur = head
visit =set()
while cur:
if cur in visit:
return True
visit.add(cur)
cur = cur.next
return False
|
5.环形链表2#
题目描述#
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
题解：还是上面两种#
set
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def detectCycle(self, head):
visited = set()
while head:
if head in visited:
return head
visited.add(head)
head = head.next
return None
|
快慢指针：懒得找了，比较经典吧
6.合并两个有序列表#
题目描述#
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
题解：虚拟头节点：挺有思想的，值得学习；我当时忘记处理剩下的剩余链表了
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
| class Solution:
def mergeTwoLists(
self,
list1: Optional[ListNode],
list2: Optional[ListNode]
) -> Optional[ListNode]:
dummy = ListNode()
cur = dummy
while list1 and list2:
if list1.val <= list2.val:
cur.next = list1
list1 = list1.next
else:
cur.next = list2
list2 = list2.next
cur = cur.next
if list1:
cur.next = list1
else:
cur.next = list2
return dummy.next
|
7.again 两数相加#
题目描述：#
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
题解：#
模拟竖式加法，逐位计算两个链表节点的值，加上进位，然后用尾插法把每一位结果连接成新的链表。
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
| # Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
cur = dummy
carry = 0
while l1 or l2 or carry:
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
total = val1 + val2 + carry
carry = total // 10
digit = total % 10
cur.next = ListNode(digit)
cur = cur.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
return dummy.next
|
8.删除链表倒数第n个节点#
题目描述：#
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
题解：#
依旧快慢指针这一块
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| # Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0,head)
slow,fast = dummy,dummy
for i in range(n):
fast = fast.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next
|
9.两两交换链表中的结点#
题目描述：#
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
题解：#
使用虚拟头节点 dummy 和一个前驱指针 pre，每次找到相邻的两个节点进行交换，然后把 pre 移动到交换后的第一个节点（原来的第一个节点），继续处理下一对
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0, head)
pre = dummy
while pre.next and pre.next.next:
first = pre.next
second = first.next
# 交换两个节点
first.next = second.next
second.next = first
pre.next = second
# 移动到下一组
pre = first
return dummy.next
|
10.K个一组翻转链表#
题目描述：#
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 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
28
29
30
31
32
33
34
35
| class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
dummy = ListNode()
dummy.next = head
groupprv = dummy
while True:
kth = groupprv
# 找第 k 个节点
for _ in range(k):
kth = kth.next
if not kth:
return dummy.next
groupnext = kth.next
# 翻转当前组
cur = groupprv.next
tail = groupnext
while cur != groupnext:
nxt = cur.next
cur.next = tail
tail = cur
cur = nxt
# 更新连接关系
tmp = groupprv.next
groupprv.next = kth
groupprv = tmp
|
11.排序列表#
题目描述：#
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
1.我要暴力了啊：冒泡排序
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
# 计算链表长度
cnt = 0
cur = head
while cur:
cnt += 1
cur = cur.next
# 冒泡排序
for i in range(cnt - 1):
cur = head
for j in range(cnt - 1 - i):
if cur.val > cur.next.val:
cur.val, cur.next.val = cur.next.val, cur.val
cur = cur.next
return head
2.归并排序
不断把链表从中间拆成两半，直到每个链表只剩一个节点；然后再将两个有序链表不断合并，最终得到完整的有序链表。
递归；归并排序
思路很重要，代码挺简单的，自己看
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
| class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 只有 0 个或 1 个节点，不需要排序
if not head or not head.next:
return head
# ====================
# 1. 快慢指针找中点
# ====================
slow = head
fast = head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# ====================
# 2. 从中间断开
# ====================
mid = slow.next
slow.next = None
# ====================
# 3. 分别排序左右两部分
# ====================
left = self.sortList(head)
right = self.sortList(mid)
# ====================
# 4. 合并两个有序链表
# ====================
return self.merge(left, right)
def merge(self, l1, l2):
dummy = ListNode()
cur = dummy
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
# 剩下的直接接上
if l1:
cur.next = l1
else:
cur.next = l2
return dummy.next
|
3.一个为了解题的简单方法，挺没意思的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
seen = []
cur = head
while cur:
seen.append(cur.val)
cur = cur.next
seen.sort()
cur = head
for i in seen:
cur.val = i
cur = cur.next
return head
|
12.合并k个升序列表#
题目描述：#
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
题解：#
不道德的解法1：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| # Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
values=[]
for head in lists:
while head:
values.append(head.val)
head=head.next
values.sort()
ptr = ListNode()
dummy = ListNode()
dummy.next = ptr
for x in range(len(values)):
cur = ListNode(values[x])
ptr.next = cur
ptr=cur
return dummy.next.next
|
13.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) 的平均时间复杂度运行。
解法：哈希表加双向链表或者你熟悉LinkedHashmap也好做#
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
89
90
| class Node:
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
# 哈希表
self.cache = {}
# 双向链表虚拟头尾
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
# 最近使用，移动到头部
self._remove(node)
self._add_to_head(node)
return node.value
def put(self, key: int, value: int) -> None:
# key 已经存在
if key in self.cache:
node = self.cache[key]
node.value = value
# 更新后也是最近使用
self._remove(node)
self._add_to_head(node)
else:
# 创建新节点
node = Node(key, value)
self.cache[key] = node
# 放到头部
self._add_to_head(node)
# 超过容量
if len(self.cache) > self.capacity:
# 删除尾部节点
last = self.tail.prev
self._remove(last)
del self.cache[last.key]
def _remove(self, node):
prev_node = node.prev
next_node = node.next
prev_node.next = next_node
next_node.prev = prev_node
def _add_to_head(self, node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
|
