234. 回文链表[easy]

判断一个链表是否是回文链表 1-2-3-2-1是,1-2-3不是

两种方法,简单明了的是将链表转换为数组然后通过双指针判断左右指针的值是否相等,到循环结束还是相等那就返回true,否则就是false,缺点是空间复杂度ON

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def isPalindrome(self, head):
"""
:type head: Optional[ListNode]
:rtype: bool
"""
curr = head
list_ = []
while curr:
list_.append(curr.val)
curr = curr.next

left, right = 0, len(list_)-1
while left < right:
if list_[left] == list_[right]:
left += 1
right -= 1
else:
return False
return True
  • 第二种比较麻烦的是先找到链表中点,然后将后半段链表翻转,再和前半段一一对比
  • 怎么找中点,可以通过快慢指针遍历链表,fast是slow两倍,这样fast结束的时候slow就在中点或者中点前一个节点。
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
if not head or not head.next:
return True

# 1. 找到链表的中点
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 循环结束后, slow 指向中点 (或中点前一个节点)

# 2. 反转后半部分链表
second_half_head = self.reverse_list(slow)

# 3. 比较前半部分和反转后的后半部分
first_half_head = head
while second_half_head:
if first_half_head.val != second_half_head.val:
return False
first_half_head = first_half_head.next
second_half_head = second_half_head.next

return True

def reverse_list(self, head: ListNode) -> ListNode:
"""一个标准的链表反转辅助函数"""
prev = None
curr = head
while curr:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
return prev

148. 排序链表

给你一个链表,将其从小到大排序后返回要求复杂度Onlogn,和O1

  • 思路:由于复杂度是nlogn所以只能是高效的排序算法,如快速排序,归并排序和堆排序,这里显然用归并最符合。归并的思想就是先找到中点然后左边右边分别递归排序后再合在一起排序一次得到完整的内容。
  • 放在链表里就是:先找到链表中点将其分成左右两个链表,然后对左右链表再次进行分解,分成左右两个链表,一直重复直到不能再分(只有一个节点的子链表)后结束,显然用递归操作。
  • 然后就是合并链表,合并有序链表和之前做过的题一模一样,因为单个节点的子链表本身就有序,所以只需要慢慢的按顺序拼接起来就能得到排好序的链表了。
  • 实现过程:首先设定好递归停止条件,也就是链表的head为none或者head.next为none就返回head。然后设置快慢指针来获取中点,注意fast初始值是head.next而不是head这样能保证fast结束后slow在中点或者中点之前一个节点(当然fast=head也可以,只是最后结果slow会在中点或者中点的后一个节点,这样还需要额外的一个prev来指向它之前的节点)。
  • 然后将slow.next保存作为右边链表的头节点后切断链表slow.next=none, 最后通过递归的方式分别把左边的链表头节点head和右边链表头节点mid再次调用sortList()自己,注意程序是先递归left_sorted = self.sortList(head),直到它完全处理完后再调用right_sorted = self.sortList(mid)的,例如:sortList([4, 2, 1, 3])→left_sorted = sortList([4, 2])→left_sorted = sortList([4])→[4],此时跳出sortList([4])后在sortList([4,2])这个作用域里它得到了left_sorted的结果,接下来到了right_sorted = self.sortList([2]),同样得到结果right_sorted=[2],最后将其merge后返回得到了[2,4],也就是sortList([4,2])返回了left_sorted[2,4],于是开始执行right_sorted = self.sortList([1,3]),同理最后得到[1,3],最后在merge返回了排好序的[1,2,3,4]
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
class Solution(object):
def sortList(self, head):
"""
:type head: Optional[ListNode]
:rtype: Optional[ListNode]
"""

if head is None or head.next is None:
return head

fast, slow = head.next, head

while fast and fast.next:
fast = fast.next.next
slow = slow.next

mid = slow.next
slow.next = None

left_sorted = self.sortList(head)
right_sorted = self.sortList(mid)

return self.merge(left_sorted, right_sorted)

def merge(self, l1, l2):
dummy_head = ListNode(0)
curr = dummy_head

while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next

if l1:
curr.next = l1
else:
curr.next = l2

return dummy_head.next

23. 合并 K 个升序链表[hard]

给定一个list,里面装了k个已经排好序的链表,让你合并成一整个并返回

  • 有几种做法,最佳是归并排序+链表合并,还有堆排序或者顺序合并做法,其中顺序合并最容易被想到,也是我直接想到的方法,但是缺点就是k如果很大的话可能超时,复杂度为O(k^2N),还想到的就是直接把链表拼在一起再整个排序。
  • 我采取的是顺序合并:做法如下→直接将第一个链表作为基准,和后续的链表进行逐一合并,比如l1+l2的结果作为l1,再和l3,l4,…逐一合并。关键点是怎么把合并完后的链表作为下一个l1?答案就是在循环内每次循环都创建一个dummy_head来储存合并后的链表,这样才能获得这个链表和后续链表合并,以及合并到最后结束后显然l1还在,但是后面没有链表了,所以直接返回l1
  • 顺序合并则是和之前做过的题一样操作。开头还需要注意的是lists = [lst for lst in lists if lst]防止出现lists=[[]]的情况
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
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[Optional[ListNode]]
:rtype: Optional[ListNode]
"""
lists = [lst for lst in lists if lst] #

if not lists:
return None
if len(lists) == 1:
return lists[0]

# dummy_head = ListNode(0)
# curr = dummy_head

i = 1
l1 = lists[0]
while i < len(lists):
l2 = lists[i]
# 改动 2: 为本次合并创建一个全新的、临时的“工作台”
temp_dummy = ListNode(0)
temp_curr = temp_dummy

while l1 and l2:
if l1.val <= l2.val:
temp_curr.next = l1
l1 = l1.next
else:
temp_curr.next = l2
l2 = l2.next
temp_curr = temp_curr.next

temp_curr.next = l1 if l1 else l2
l1 = temp_dummy.next#
i += 1

return l1 #

94. 二叉树的中序遍历

如题 遍历顺序:左-根-右,最后返回节点值组成的数组

  • 递归对于遍历树一般是最常见的,一般是设置跳出条件if,然后直接按顺序写递归就可以了,这题是中序遍历dfs,那就是先写左递归,然后读取值,再然后右递归即可,一般都会在函数里写一个用于递归的函数,不然会影响主函数的返回值(这题是数组)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: Optional[TreeNode]
:rtype: List[int]
"""
# if root is None:
# return []
# # 先遍历左子树
# left = self.inorderTraversal(root.left)
# right = self.inorderTraversal(root.right)

# return left + [root.val] + right
res = []
def dfs(node):
if node is None:
return
dfs(node.left)
res.append(node.val)
dfs(node.right)
dfs(root)
return res
  • 也可以按照我注释里写的另一种方法来,也就是递归带返回值的,那么返回值就一定要有能传递递归内容的地方(这题是[root.val])

104. 二叉树的最大深度

如题,最后返回深度数值

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
import collections
class Solution(object):
def maxDepth(self, root):
"""
:type root: Optional[TreeNode]
:rtype: int
"""
if root is None:
return 0
# # 如果树不为空,那么它的最大深度等于 1 (当前节点) + 其左、右子树中较大的那个深度
# DFS
# left = self.maxDepth(root.left)
# right = self.maxDepth(root.right)
# return max(left, right) + 1

# BFS
queue = collections.deque([root])
depth = 0

while queue:
depth += 1
level_size = len(queue)

for _ in range(level_size):
node = queue.popleft()

if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return depth
  • 第一种方法还是递归,类似后续遍历,需要先知道左右节点才能计算,所以这是带返回值的递归,在函数里return max(left, right)+ 1,这个+1表示当前节点所在层
  • 第二种方法就是BFS,也就是用队列来储存每一层的节点,然后计算层数。具体就是先确定临界条件,如果root为空就返回0,然后下一步就是定义队列 collections.deque([root]),然后再根据queue是否为空来判断循环是否继续,每一次循环就表示一层,关键就是通过level_size = len(queue)知道每一层有多少节点,也就是说为了能够遍历每个节点,我们得先知道每层有多少个节点,然后

102. 二叉树的层序遍历

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
import collections
class Solution(object):
def levelOrder(self, root):
"""
:type root: Optional[TreeNode]
:rtype: List[List[int]]
"""
if root is None:
return []

queue = collections.deque([root])
res = []
while queue:
level_size = len(queue)
tmp_res = []
for _ in range(level_size):
node = queue.popleft()
tmp_res.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(tmp_res)

return res

226. 翻转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def invertTree(self, root):
"""
:type root: Optional[TreeNode]
:rtype: Optional[TreeNode]
"""
if root is None:
return None

root.left , root.right = root.right, root.left

self.invertTree(root.left)
self.invertTree(root.right)

return root

101. 对称二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def isSymmetric(self, root):
"""
:type root: Optional[TreeNode]
:rtype: bool
"""
return self.isMirror(root.left, root.right)

def isMirror(self, p, q):
if p is None and q is None:
return True
if p is None or q is None or p.val != q.val:
return False

outer_is_mirror = self.isMirror(p.left, q.right)
inner_is_mirror = self.isMirror(p.right, q.left)

return outer_is_mirror and inner_is_mirror

543. 二叉树的直径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def diameterOfBinaryTree(self, root):
"""
:type root: Optional[TreeNode]
:rtype: int
"""
self.maxLength = 0
self.depth(root)

return self.maxLength

def depth(self, node):
# 以父节点的视角来看,就是计算他的两个直系孩子分别最长有多长,最后再加上自己(+1),而每一个节点都可以当作父节点
if node is None:
return 0

left = self.depth(node.left)
right = self.depth(node.right)

self.maxLength = max(self.maxLength, left + right)

return max(left, right) + 1

108. 将有序数组转换为二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: Optional[TreeNode]
"""
return self.build(nums, 0, len(nums) - 1)

def build(self, nums, left, right):
if left > right:
return None

mid = (left + right)//2
root = TreeNode(nums[mid])

root.left = self.build(nums, left, mid - 1) #
root.right = self.build(nums, mid + 1, right) #

return root