题目列表
链表
面试题06. 从尾到头打印链表
面试题18. 删除链表的节点
面试题22. 链表中倒数第k个节点
面试题24. 反转链表(标记)
面试题25. 合并两个排序的链表
面试题35. 复杂链表的复制（medium）
面试题36. 二叉搜索树与双向链表(medium)
面试题52. 两个链表的第一个公共节点
栈
面试题09. 用两个栈实现队列
面试题30. 包含min函数的栈
面试题59 - I. 滑动窗口的最大值
链表：
面试题06. 从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
递归法：
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
return self.reversePrint(head.next) +[head.val] if head else []
栈：
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
stack = []
while head:
stack.append(head.val)
head = head.next
return stack[::-1]
非常简单
面试题18. 删除链表的节点
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
注意：此题对比原题有改动
示例 1:
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
说明：
题目保证链表中节点的值互不相同
若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点
class Solution:
def deleteNode(self, head: ListNode, val: int) -> ListNode:
if head.val == val: return head.next
pre, cur = head, head.next
while cur and cur.val != val:
pre, cur = cur, cur.next
if cur:
pre.next = cur.next
return head
面试题22. 链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
p = q = head
count = 0
while q:
if count >= k:
p = p.next
count += 1
q = q.next
return p if count >= k else None
写法2，同样思路不同写法
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
slow = head
fast = head
for _ in range(k):
if not fast: return None
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
return slow
面试题24. 反转链表
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
限制：0 <= 节点个数 <= 5000
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
pre = None
curr = head
while curr:
tmp = curr.next
curr.next = pre
pre = curr
curr = tmp
return pre
emmm,每次都头大，来回来去的搞混
面试题25. 合并两个排序的链表
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
限制：0 <= 链表长度 <= 1000
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0)
node = dummy
while l1 and l2:
if l1.val > l2.val:
node.next = l2
l2 = l2.next
else:
node.next = l1
l1 = l1.next
node = node.next
node.next = l1 if l1 else l2
return dummy.next
基本操作。
面试题35. 复杂链表的复制
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
解法1 深度优先
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
def dfs(head):
if not head: return None
if head in visited:
return visited[head]
copy = Node(head.val, None, None)
visited[head] = copy
copy.next = dfs(head.next)
copy.random = dfs(head.random)
return copy
visited = {}
return dfs(head)
还有迭代和广度优先的方法，觉得复杂，不做了；
面试题36. 二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。
有点难？
[图片上传中...(image.png-f13ed5-1589009921053-0)]
要求不能创建任何新的节点，只能调整树中节点指针的指向。
为了让您更好地理解问题，以下面的二叉搜索树为例：
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
这狗题目好难
面试题52. 两个链表的第一个公共节点
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：
在节点 c1 开始相交。
示例 1：
输入：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 个节点。
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
p1 = headA
p2 = headB
while p1 != p2:
p1 = headB if p1 is None else p1.next
p2 = headA if p2 is None else p2.next
return p1
======================================================
栈
面试题09. 用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
示例 1：
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]
示例 2：
输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
class CQueue:
def __init__(self):
self.A, self.B = [], []
def appendTail(self, value: int) -> None:
self.A.append(value)
def deleteHead(self) -> int:
if self.B:
return self.B.pop()
if not self.A:
return -1
while self.A:
self.B.append(self.A.pop())
return self.B.pop()
deleteHead解析：
删除队首deleteHead()函数： 有以下三种情况。
当栈 B 不为空： B中仍有已完成倒序的元素，因此直接返回 B 的栈顶元素。
否则，当 A 为空： 即两个栈都为空，无元素，因此返回 -1−1 。
否则： 将栈 A 元素全部转移至栈 B 中，实现元素倒序，并返回栈 B 的栈顶元素。
面试题30. 包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.
解题思路：
push(x) 函数： 重点为保持栈 B 的元素是 非严格降序 的。
将 x 压入栈 A （即 A.add(x) ）；
若 ① 栈 B 为空 或 ② x 小于等于 栈 B 的栈顶元素，则将 xx 压入栈 BB （即 B.add(x) ）。
pop() 函数： 重点为保持栈 A,B 的 元素一致性 。
执行栈 A 出栈（即 A.pop() ），将出栈元素记为 y ；
若 y 等于栈 B 的栈顶元素，则执行栈 B 出栈（即 B.pop() ）。
top() 函数： 直接返回栈 A 的栈顶元素即可
min() 函数： 直接返回栈 B 的栈顶元素即可
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.s1 = []
self.s2 = []
def push(self, x: int) -> None:
self.s1.append(x)
if not self.s2 or self.s2[-1] >= x:
self.s2.append(x)
def pop(self) -> None:
if self.s1.pop() == self.s2[-1]: ##这注意下
self.s2.pop()
def top(self) -> int:
return self.s1[-1]
def min(self) -> int:
return self.s2[-1]
面试题59 - I. 滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
暴力的遍历法解题
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if not nums or k== 0: return []
res = []
for i in range(0, len(nums)-k+1):
res.append(max(nums[i:i+k]))
return res
暴力法的算法的时间复杂度是O(n)，当要求优化算法，算法时间复杂读是O(1)时，使用一个队列来记录最大值
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if not nums or k== 0: return []
deque = collections.deque()
res = []
for i in range(k):
while deque and deque[-1] < nums[i]: deque.pop()
deque.append(nums[i])
res.append(deque[0])
for i in range(k, len(nums)):
if deque[-1] == nums[i-k]: deque.popleft()
while deque and deque[-1] < nums[i]: deque.pop()
deque.append(nums[i])
res.append(deque[0])
return res
面试题59 - II. 队列的最大值
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
示例 1：
输入:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
示例 2：
输入:
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]
均摊时间复杂度为O(1)
import queue
class MaxQueue:
def __init__(self):
self.deque = queue.deque()
self.queue = queue.Queue()
def max_value(self) -> int:
return self.deque[0] if self.deque else -1
def push_back(self, value: int) -> None:
while self.deque and self.deque[-1] < value:
self.deque.pop()
self.deque.append(value)
self.queue.put(value)
def pop_front(self) -> int:
if not self.deque:
return -1
ans = self.queue.get()
if ans == self.deque[0]:
self.deque.popleft()
return ans
