leetcode题目按类型
链表
遍历框架
链表遍历框架,兼具迭代和递归结构:
/* 基本的单链表节点 */
class ListNode {
int val;
ListNode next;
}
void traverse(ListNode head) {
for (ListNode p = head; p != null; p = p.next) {
// 迭代访问 p.val
}
}
void traverse(ListNode head) {
// 递归访问 head.val
traverse(head.next)
}
Python：
1
2
3
4
5
6
7
8
9
10
11
12
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def traverse(head)：
p = head
while p:
# 迭代访问 p.val
p = p.next
def traverse(head)：
# 递归访问 head.val
traverse(head.next)
总结
概念
-
链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。 链表通常可以衍生出循环链表，静态链表，双链表等。对于链表使用，需要注意头结点的使用。
-
链表中的“哨兵”节点是解决边界问题的，不参与业务逻辑。如果我们引入“哨兵”节点，则不管链表是否为空，head指针都会指向这个“哨兵”节点。我们把这种有“哨兵”节点的链表称为带头链表，相反，没有“哨兵”节点的链表就称为不带头链表。
基于python的自建链表类（list to linklist)
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
def initList(self, data):
# 判断是否为空
if len(data) == 0:
return
else:
# 创建头结点
self.head = ListNode(data[0])
# 头结点
r = self.head
# 指针
p = self.head
# 逐个为 data 内的数据创建结点, 建立链表
for i in data[1:]:
node = ListNode(i)
p.next = node
p = p.next
return r
def linklist2List(self, linklist):
List = []
while linklist:
List.append(linklist.val)
linklist = linklist.next
return List
1
2
3
4
5
6
7
8
9
10
11
12
# 使用
l1 = [1,2,4]
l2 = [1,3,4]
List2Linklist = ListNode()
l1 = List2Linklist.initList(l1)
l2 = List2Linklist.initList(l2)
print(l1.val, "->", l1.next.val, "->", l1.next.next.val)
print(l2.val, "->", l2.next.val, "->", l2.next.next.val)
print(List2Linklist.linklist2List(l1))
# List2Linklist.printLinklist(result)
哨兵节点使用
把prev期初所在的位置命名为prehead，这样prev再怎么变都可以找到其起始地址。
1
2
3
4
5
6
7
prehead = ListNode(-1) # 哨兵节点，让我们容易的返回合并后的链表
prev = prehead # prev指针，我们调整它的next指针，直到l1或者l2某一个指向了NULL
···
return prehead.next # 返回入口地址
Python的ListNode类
1
2
3
4
5
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
🚩21. 合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
1
2
3
4
5
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
2️⃣ (1.5h)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 标准
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
# maintain an unchanging reference to node ahead of the return node.
prehead = ListNode(-1) # 哨兵节点，让我们容易的返回合并后的链表
prev = prehead # prev指针，我们调整它的next指针，直到l1或者l2某一个指向了NULL
while l1 and l2:
if l1.val <= l2.val:
prev.next = l1
l1 = l1.next # 注意l1的指针也要移动
else:
prev.next = l2
l2 = l2.next
prev = prev.next # 指向下一个值
prev.next = l1 if l1 is not None else l2
return prehead.next # 返回入口地址
1
2
3
4
5
6
7
8
9
10
11
12
13
14
l1 = [1,2,4]
l2 = [1,3,4]
List2Linklist = ListNode()
l1 = List2Linklist.initList(l1)
l2 = List2Linklist.initList(l2)
solution = Solution()
result = solution.mergeTwoLists(l1,l2)
print(l1.val, "->", l1.next.val, "->", l1.next.next.val)
print(l2.val, "->", l2.next.val, "->", l2.next.next.val)
print(List2Linklist.linklist2List(result))
# List2Linklist.printLinklist(result)
✅(10m)206. 反转链表
反转一个单链表。
1
2
3
4
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# 申请两个节点，pre和 cur，pre指向None
pre = None
cur = head
# 遍历链表，while循环里面的内容其实可以写成一行
# 这里只做演示，就不搞那么骚气的写法了
while cur:
# 记录当前节点的下一个节点
tmp = cur.next
# 然后将当前节点指向pre
cur.next = pre
# pre和cur节点都前进一位
pre = cur
cur = tmp
return pre
2️⃣ (1.5h)
注意要返回Newhead = pre
3️⃣递归解法(🚩)
1
2
3
4
5
6
7
8
9
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
# digui
if not head or not head.next: # 只有当前节点
return head
last = self.reverseList(head.next) # 拆解为子问题
head.next.next = head
head.next = None
return last
3️⃣迭代解法
1
2
3
4
5
6
7
8
9
# 迭代
if not head: # 只有当前节点
return head
pre, cur = None, head
while cur:
tmp = cur.next
cur.next = pre
pre, cur = cur, tmp
return pre
✅ (15m) 删除链表中给定的节点
请编写一个函数，使其可以删除某个链表中给定的(非末尾)节点，你将只被给定要求被删除的节点。
现有一个链表 – head = [4,5,1,9]，它可以表示为:
1
示例 1:输入: head = [4,5,1,9], node = 5输出: [4,1,9]解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.示例 2:输入: head = [4,5,1,9], node = 1输出: [4,5,9]解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
1
class Solution: def deleteNode(self, node): """ :type node: ListNode :rtype: void Do not return anything, modify node in-place instead. """ node.val = node.next.val node.next = node.next.next
✅(50m) 203. 移除链表元素
删除链表中等于给定值 val 的所有节点。
1
示例:输入: 1->2->6->3->4->5->6, val = 6输出: 1->2->3->4->5
哨兵节点广泛应用于树和链表中，如伪头、伪尾、标记等，它们是纯功能的，通常不保存任何数据，其主要目的是使链表标准化，如使链表永不为空、永不无头、简化插入和删除。
在这里哨兵节点将被用于伪头。
1
# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def removeElements(self, head: ListNode, val: int) -> ListNode: if not head: return None while head and head.val == val: if head.next: head = head.next else: head.next = None return None prehead = head while head.next: if head.next.val == val and head.next.next: head.next = head.next.next elif head.next.val == val and not head.next.next: head.next = None else: head = head.next return prehead
1
# 官方class Solution: def removeElements(self, head: ListNode, val: int) -> ListNode: sentinel = ListNode(0) # 哨兵节点 sentinel.next = head prev,curr = sentinel,head while curr: if curr.val == val: # 双指针，如果curr删除，prev同时移动 prev.next == curr.next else: prev = curr curr = curr.next return sentinel.next
✅(90m)234. 回文链表
请判断一个链表是否为回文链表。
1
示例 1:输入: 1->2输出: false示例 2:输入: 1->2->2->1输出: true进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
1
# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def isPalindrome(self, head: ListNode) -> bool:
1
# 官解，数组def isPalindrome(self, head: ListNode) -> bool: vals = [] current_node = head while current_node is not None: vals.append(current_node.val) current_node = current_node.next return vals == vals[::-1]
1
# 官解，反转后半部分链表# 方法三：# 避免使用 O(n)O(n) 额外空间的方法就是改变输入。# 我们可以将链表的后半部分反转(修改链表结构)，然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例，因为使用该函数的人不希望链表结构被更改。# 算法：# 我们可以分为以下几个步骤：# 找到前半部分链表的尾节点。# 反转后半部分链表。# 判断是否为回文。# 恢复链表。# 返回结果。
2️⃣
On,On版本
1
class Solution: def isPalindrome(self, head: ListNode) -> bool: prehead = head ln = [] while head: ln.append(head.val) head = head.next if len(ln) <= 1: return True if ln[:len(ln)//2] == ln[-(len(ln)//2):][::-1]: # 注意！负号优先级大于// return True else: return False
3️⃣
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
# 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: ListNode) -> bool:
if not head or not head.next:
return True
# 1. Find middle node by fast and slow pointer
slow = fast = head
while fast and fast.next:
p = slow
q = fast.next
slow = slow.next
fast = fast.next.next
# print(slow)
# 2. odd case
if fast:
p = slow
slow = slow.next
q = fast
# 3. reverse()
def reverse(head):
pre,cur = None,head
while cur:
tmp = cur.next
cur.next = pre
pre,cur = cur,tmp
return pre
# 4 & 5. compare ListNode and restore ListNode
left = head
right = reverse(slow) # middle node
# print(p,q)
while right != None:
# print(left.val , right.val)
if left.val != right.val:
p.next = reverse(q)
return False
left = left.next
right = right.next
p.next = reverse(q)
# print(head)
return Trueclass Solution:
def isPalindrome(self, head: ListNode) -> bool:
if not head or not head.next:
return True
# 1. Find middle node by fast and slow pointer
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# print(slow)
# 2. odd case
if fast:
slow = slow.next
# 3. reverse()
def reverse(head):
pre,cur = None,head
while cur:
tmp = cur.next
cur.next = pre
pre,cur = cur,tmp
return pre
# 4. compare ListNode
left = head
right = reverse(slow) # middle node
while right != None:
# print(left.val , right.val)
if left.val != right.val:
return False
left = left.next
right = right.next
return True
注意：
1.运算符优先级，注意符号优先级很高，大于除号！！
-
注意用快慢指针来找中点
- 注意如果是奇数的话判断fast非None则要再加1位
- 记录下p，q和 ` p.next = reverse(q)` 可恢复原链表
✅(50m) 2. 两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
1
示例：输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -> 0 -> 8原因：342 + 465 = 807
1
# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: prehead = ListNode(-1) newlinklist = prehead carry = 0 while l1 and l2: newlinklist.next = ListNode((l1.val+l2.val + carry)%10) # 新建linklist的方法，注意不能linklist.val == newlinklist = newlinklist.next carry = (l1.val+l2.val + carry)//10 l1, l2 = l1.next, l2.next while l1 and l2 is None: newlinklist.next = ListNode((l1.val + carry)%10) newlinklist = newlinklist.next carry = (l1.val + carry) l1 = l1.next while l2 and l1 is None: newlinklist.next = ListNode((l2.val + carry)%10) newlinklist = newlinklist.next carry = (l2.val + carry) l2 = l2.next if carry == 1: newlinklist.next = ListNode(carry) return prehead.next
1
1
1
1
✅ 206. 反转链表
反转一个单链表。
1
示例:输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL
进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
1
class Solution(object): def reverseList(self, head): """ :type head: ListNode :rtype: ListNode """ # 申请两个节点，pre和 cur，pre指向None pre = None cur = head # 遍历链表，while循环里面的内容其实可以写成一行 # 这里只做演示，就不搞那么骚气的写法了 while cur: # 记录当前节点的下一个节点 tmp = cur.next # 然后将当前节点指向pre cur.next = pre # pre和cur节点都前进一位 pre = cur cur = tmp return pre
2️⃣ (30m)
1
class Solution(object): def reverseList(self, head): cur = head # 注意是从head开始 pre = None while cur: nexttmp = cur.next cur.next = pre pre = cur cur = nexttmp return pre # 返回的是起始点
🚩25. K 个一组翻转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
1
示例：给你这个链表：1->2->3->4->5当 k = 2 时，应当返回: 2->1->4->3->5当 k = 3 时，应当返回: 3->2->1->4->5
说明：
你的算法只能使用常数的额外空间。 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def reverseList(self, head):
while cur:
nexttmp = cur.next
cur.next = pre
pre = cur
cur = nexttmp
return pre # 返回的是起始点
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
cur = head # 注意是从head开始
pre = None
reverseList()
2️⃣
🚩23. 合并K个排序链表
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
1
2
3
4
5
6
7
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
2️⃣
✅(20m)141. 环形链表
难度简单916
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
示例 1：
1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
1
法1：放到set里class Solution: def hasCycle(self, head: ListNode) -> bool: # if not head: return False # set_node = set() # while head: # if head in set_node: # return True # set_node.add(head) # head = head.next # return False
1
法二：快慢指针class Solution: def hasCycle(self, head: ListNode) -> bool: if not head: return False slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if fast == slow: return True return False
注意：
- 注意链表是可以放到set里的，判断链表相等要满足value和next都相等
- set是用add和remove的，O(1)时间复杂度
🚩(20m) 142. 环形链表 II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
if not head: return None
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast == slow:
fast = head
while fast:
if fast == slow: # 注意考虑特殊情况第一个环点为0时要先判断两个指针是否相同
return fast
slow = slow.next
fast = fast.next
✅(10m)86. 分隔链表
难度中等357
给你一个链表和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例：
1
2
输入：head = 1->4->3->2->5->2, x = 3
输出：1->2->2->4->3->5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
node1 = ListNode(-1)
node2 = ListNode(-1)
prenode1 = node1
prenode2 = node2
while head:
if head.val < x:
node1.next = head
node1 = node1.next
else:
node2.next = head
node2 = node2.next
head = head.next
node1.next, node2.next = prenode2.next, None
return prenode1.next
总结
- 遍历结束后，我们将large 的 next 指针置空，这是因为当前节点复用的是原链表的节点，而其 next 指针可能指向一个小于 x 的节点，我们需要切断这个引用。
160. 相交链表
难度简单957
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：
在节点 c1 开始相交。
示例 1：
1
2
3
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
OnOn版本
1
2
3
4
5
6
7
8
9
10
11
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
set_n = set()
while headA:
set_n.add(headA)
headA = headA.next
while headB:
if headB in set_n:
return headB
headB = headB.next
return None
我的OnO1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
preheadA = headA
preheadB = headB
STATE_A = STATE_B = True
while headA and headB:
print(headA.val,headB.val,' ')
if headA == headB:
return headA
headA = headA.next
headB = headB.next
if headA == None and STATE_A: # 要先判断下
headA = preheadB
STATE_A = False
if headB == None and STATE_B:
headB = preheadA
STATE_B = False
return None
大佬OnO1版本
1
2
3
4
5
6
7
8
9
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
curr1, curr2 = headA, headB
while curr1 != curr2:
curr1 = curr1.next if curr1 else headB
curr2 = curr2.next if curr2 else headA
return curr1
🚩(60m)92. 反转链表 II
难度中等674
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明: 1 ≤ m ≤ n ≤ 链表长度。
示例:
1
2
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
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
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
# 官解
if not head: # 只有当前节点
return None
# dummy = head
# pos = 1
# i = dummy
cur, prev = head, None
# while pos < m:
while m > 1: # 一直循环到m==1的情况
prev = cur
cur = cur.next
m, n = m-1, n-1 # 注意，这样就不需要记录当前位置
# pos += 1
# j = dummy
tail, con = cur, prev
while n:
thrid = cur.next
cur.next = prev
prev, cur = cur, thrid
n -= 1
# pos += 1
if con: # 如果i从1开始，则con==None，无next，则直接令head = prev
con.next = prev
else:
head = prev
tail.next = cur
return head
3️⃣ (40m) 注意停止条件是 while head:
注意：
- m, n = m-1, n-1 # 注意，这样就不需要记录当前位置
- 最后要分情况，是否直接从第一个节点就开始反转
🚩 (1.5h) 146. LRU缓存机制
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值(总是正数)，否则返回 -1。 写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
1
2
3
4
5
6
7
8
9
10
11
12
13
示例:
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得关键字 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得关键字 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
2️⃣
LRU 双向链表+哈希 双链表数据结构：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class DLinkedNode:
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.cache = dict()
# 使用伪头部和伪尾部节点
self.head = DLinkedNode()
self.tail = DLinkedNode()
self.head.next = self.tail
self.tail.prev = self.head
self.capacity = capacity
self.size = 0
