【基础】leetcode 24 两两交换链表中的节点
思路基本正确，实现的时候还是被绕进去了
首先，想清楚为什么要使用虚拟头节点
其次，应该写框架：1）while条件是什么 2）用几个指针去贯穿，是cur还是pre+cur？ 3）每次循环完条件怎么变化？ 4）交换逻辑怎么写？（写了两种，一种只需要一个tmp，一种需要两个tmp但更好理解一些） 5）返回用head还是dummy_head？估计很快就会忘掉唉，只要想清楚，其实整体不难
todo：再刷
# python3
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy_head = ListNode(next=head)
cur = dummy_head
while cur.next != None and cur.next.next != None:
fst = cur.next
snd = cur.next.next
cur.next = snd
fst.next = snd.next
snd.next = fst
# tmp = cur.next
# cur.next = cur.next.next
# tmp.next = cur.next.next
# cur.next.next = tmp
cur = cur.next.next # 下一次交换
return dummy_head.next
【基础】leetcode 19 删除链表的倒数第N个节点
一开始在想，那不就是正数第x个节点，删掉不就行了嘛，然后，发现，链表不知道length
想到双指针之后自己的整体思路和实现都没毛病，赞！
# python3
# 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_head = ListNode(next=head)
i, j = dummy_head, dummy_head
step = n
while j.next != None and step > 0:
step -= 1
j = j.next
while j.next != None:
j = j.next
i = i.next
i.next = i.next.next
return dummy_head.next
【基础】面试题 02.07. 链表相交
这题不会，自己完全没有思路
首先，要明确一点，单向链表因为只有一个next指向下一个节点的地址，所以两个链表相交了就不会再分开了，参考：https://blog.csdn.net/onlymayao/article/details/106161249
todo：《编程之美》可以看看
每道题目伪代码写完之后要思考并记录一下时间复杂度和空间复杂度谨记：head不能随便动，比如计算链表长度的时候用了headA = headA.next这样的写法，那headA就会变成None了最后
todo：值得再刷
# python3
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
lenA, lenB = 0, 0
curA, curB = headA, headB
while curA: # 不用写 !=None 了，简洁一点
lenA += 1
curA = curA.next
while curB:
lenB += 1
curB = curB.next
curA, curB = headA, headB # cur变成None了，重新赋值为head
if lenA < lenB:
curA, curB = curB, curA
lenA, lenB = lenB, lenA
for _ in range(lenA - lenB):
curA = curA.next
while curA: # 判断一个就行了，不然用and的话判断时间double
if curA == curB:
return curA
else:
curA = curA.next
curB = curB.next
return None
【基础】leetcode 142.环形链表II
自己想不出思路。这题难在逻辑推理：1）可以确定的是，快慢指针一定是在环内相遇 2）相遇的时候慢指针一定还在环的第一圈（可以想一下极端情况，最慢快指针追了慢指针一整圈才追到，这是慢指针也还是在自己的第一圈） 3）相遇的时候快指针可能已经独自在环内走过n圈了，不能确定n是多少，最小是1（不可能是0，因为只有绕一圈才能相遇），最大可能是很大，但是这些条件足够了 4）来看等式：2(x+y) = x+y+n(y+z) -》x=(n-1)(y+z)+z，n-1最小是0，理解一下，也就是说最快的情况，头节点到入口的距离=相遇点到入口的距离；其他情况，头节点到入口的距离=相遇点到入口的距离+n圈，但没关系，只要让指针分别从头节点和相遇点一直走，它们总会相遇在入口，只不过差别在于这时候从相遇点开始走的指针可能已经在环内转了n圈了，也可能还没开始转圈
然而知道思路之后还是没一次运行成功
todo：思路和实现都需要巩固
# python3
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return None
【复习】leetcode 977 有序数组的平方
没问题
【复习】209 长度最小的子数组
错了一个小细节，r-l+1忘了+1了，用时3min左右
【复习】59螺旋矩阵II
todo：再刷用时14min，知道大体思路（但是非常不细节了），实现的时候while还是for，怎么写还是需要现场再理顺一遍，就比较耗时，再加上c++的vector初始化也忘记怎么写的了
day4 语法积累
- c++ 初始化一个二维数组
vector<vector<int>> matrix(n, vector<int>(n, 0));
- c++ 写在一行
int left = 0, up = 0;
left++, up++;
注意跟python的区别
