今日任务

1. LeetCode24 两两交换链表中的节点
2. LeetCode19 删除链表的倒数第N个节点
3. LeetCode160 链表相交       
4. LeetCode142 环形链表Ⅱ



> 今日心情：今天意外在图书馆抢到了带插座的座位。在做题中确实学习了不少，收获颇丰。

资料来源：

1. [代码随想录 | LeetCode24 两两交换链表中的节点](https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
2. [代码随想录 | LeetCode19 删除链表的倒数第N个节点](https://programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
3. [代码随想录 | LeetCode160 链表相交](https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html#%E6%80%9D%E8%B7%AF)
4. [代码随想录 | LeetCode142 环形链表Ⅱ](https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#%E6%80%9D%E8%B7%AF)

### 1 LeetCode24 两两交换链表中的节点

:::info{title="题目"}
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

![image.png](https://www.misaka19327.cc/static/img/a34e6154d26720991a9647f205a5d6ed.image.png)

示例 1：
```
输入：head = [1,2,3,4]
输出：[2,1,4,3]
```
示例 2：
```
输入：head = []
输出：[]
```
示例 3：
```
输入：head = [1]
输出：[1]
```

提示：

* 链表中节点的数目在范围 [0, 100] 内
* 0 <= Node.val <= 100
:::

看了思路之后才能写得出来，确实是硬模拟，但是必须想明白一次交换的过程中，谁先操作，谁后操作（看注释）。

``` python
from typing import Optional

# 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]:
        virtual_head = ListNode(next=head)
        point = virtual_head
        if head is None:
            return None
        while True:
            if point.next is None:
                break
            if point.next.next is None:
                break
            temp1 = point.next
            temp2 = point.next.next.next  
            # 0 -> 1 -> 2 -> 3 —> 4 point -> 0 temp1 -> 1 temp2 -> 3
            point.next = point.next.next  # 0 -> 2 1 -> 2 -> 3 —> 4
            point.next.next = temp1  # 0 -> 2 -> 1 -> 2 -> 1  3 —> 4
            temp1.next = temp2  # 0 -> 2 -> 1 -> 3 —> 4
            point = temp1
        return virtual_head.next
```

### 2 LeetCode19 删除链表的倒数第N个节点

:::info{title="题目"}
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：
```
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
```
示例 2：
```
输入：head = [1], n = 1
输出：[]
```
示例 3：
```
输入：head = [1,2], n = 1
输出：[1]
```

提示：

* 链表中结点的数目为 sz
* 1 <= sz <= 30
* 0 <= Node.val <= 100
* 1 <= n <= sz
:::

一看双指针，忽然就懂了怎么做了。两个指针都指向虚拟头节点，然后先移动一个指针n次，然后两个指针一起进入循环，直到先移动的指针到达链表尾节点，此时后移动的指针指向的即为要删除的节点的前一个节点。

``` python
from typing import Optional

# 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]:
        if head.next is None:
            if n == 1:
                return None
            else:
                return head
        virtual_head = ListNode(next=head)
        before, after = virtual_head, virtual_head
        for _ in range(n):
            after = after.next
        while after is not None and after.next is not None:
            after = after.next
            before = before.next
        before.next = before.next.next
        return virtual_head.next
```        


:::warning{title="注意"}
**只要是有对头节点进行操作的可能，就需要使用虚拟头节点。永远不要忘记单链表中要实际操作的是目标节点的前一个节点。**
:::

### 3 LeetCode160 链表相交

:::info{title="题目"}
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

![image.png](https://www.misaka19327.cc/static/img/575cb8e9b34e1829fb664654b19d40b9.image.png)

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

* intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
* listA - 第一个链表
* listB - 第二个链表
* skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
* skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被视作正确答案。

示例 1：
![image.png](https://www.misaka19327.cc/static/img/98c80c0d64c780270b915501968d49fa.image.png)
```
输入：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：
![image.png](https://www.misaka19327.cc/static/img/04e07c07b7f67fc06bead1a03ead19d6.image.png)
```
输入：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：

![image.png](https://www.misaka19327.cc/static/img/9e9cef1ffeca7dd478cc93028c6ccff6.image.png)
```
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
```

提示：

* listA 中节点数目为 m
* listB 中节点数目为 n
* 1 <= m, n <= 3 * 104
* 1 <= Node.val <= 105
* 0 <= skipA <= m
* 0 <= skipB <= n
* 如果 listA 和 listB 没有交点，intersectVal 为 0
* 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]
:::

这个思路应该想到的，没想到是失策了，还是看着文档写出来的。先求得两个链表的长度，然后移动长链表的指针，移动到剩余长度和短链表相同时，两个指针一起循环移动和比较，只要两个指针指向的是同一个节点，就证明两个链表有相交。

``` python
from typing import Optional

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        length_a, length_b = 1, 1
        point_a, point_b = headA, headB
        while point_a.next is not None:
            point_a = point_a.next
            length_a += 1
        while point_b.next is not None:
            point_b = point_b.next
            length_b += 1
        # 之后length_a特指较长的那个链表
        if length_a <= length_b:
            gap = length_b - length_a
            point_a = headB
            point_b = headA
        else:
            gap = length_a - length_b
            point_a = headA
            point_b = headB
        while gap > 0:
            point_a = point_a.next
            gap -= 1
        while point_a is not None:
            if point_a == point_b:
                return point_a
            else:
                point_a = point_a.next
                point_b = point_b.next
        return None
```    

### 4 LeetCode142 环形链表Ⅱ

:::info{title="题目"}
给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

 

示例 1：

![image.png](https://www.misaka19327.cc/static/img/868f733904fce5c9deb11f3bf8c421b5.image.png)
```
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
```
示例 2：

![image.png](https://www.misaka19327.cc/static/img/32b9baa41dd01561b70c2689470d56c2.image.png)
```
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
```
示例 3：

![image.png](https://www.misaka19327.cc/static/img/6e5d1dd760dfac705c288b03c437fc78.image.png)
```
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
```

提示：

* 链表中节点的数目范围在范围 [0, 104] 内
* -105 <= Node.val <= 105
* pos 的值为 -1 或者链表中的一个有效索引
:::

这题确实学习了关于判断是否有环和如何确定进环位置的知识。

#### 4.1 链表是否有环？

设定双指针，在循环中快指针每次向前移动2个节点，慢指针每次向前移动1个节点。如果快慢指针在某一时刻指向同一个节点，那么链表中有环。如果快指针指向的节点或者快指针的下一个节点为空，那么链表无环。

推导：如果链表有环，那么快慢指针必定在某个时刻先后进环。**一旦进环，快慢指针的移动方式等效于快指针在以一次一个节点的速度靠近慢指针**。所以在环里，它俩必定相遇。

#### 4.2 如何确定进环位置？

在使用上述方法确定有环之后，使两个指针一个指向头节点，一个在原地不改变指向，两个节点同时按一次一个节点的速度移动，那么两个指针相遇的节点即为进环位置。

推导：按照之前的移动方式，**在慢指针正式进环的时候，快指针所在的节点向后看离进环位置的距离一定等于进环位置离头节点的距离**（即慢指针所移动过的距离）①。

反过来想，**快指针所在的节点向前看离慢指针（即进环位置）的距离，也是之后两个指针相遇时所在的节点向后看距离进环位置的距离**②。因为按照两个指针的移动方式，从慢指针进环开始，两个指针之间的距离会以每次一个节点的速度减少。那么由此可知，两个指针之间的距离为0时，慢指针移动过的距离就等于慢指针进环时，快指针向前看和慢指针的距离。

因为环的周长固定，如果快慢指针相遇时所在的节点向后看距离进环位置的距离是慢节点进环时快指针所在的节点向前看离进环位置的距离，那么**快慢指针相遇时所在的节点向前看距离进环位置的距离，即为慢指针进环时，快指针所在的节点向后看离进环位置的距离，也是进环位置离头节点的距离**③。所以从快慢指针相遇时所在的节点和头节点同时出发，以每次一个节点的速度移动，必定会在进环位置相遇。

![image.png](https://www.misaka19327.cc/static/img/ab909b6edddfbb915ce6e611966c278e.image.png)

如图，根据以上的推导，先得到$x = y$（①），再得到$z = z'$（②），最后得到$y' = y = x$（③）。（图中箭头方向即为所谓“向前”，“向后”的依据，箭头方向为前）

``` python
from typing import Optional

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast_point, slow_point = head, head
        while fast_point is not None and fast_point.next is not None:
            fast_point = fast_point.next.next
            slow_point = slow_point.next

            if fast_point == slow_point:
                fast_point = head
                while True:
                    if fast_point == slow_point:
                        return fast_point
                    fast_point = fast_point.next
                    slow_point = slow_point.next
        return None
```

代码随想录算法训练营第四天 | LeetCode24 两两交换链表中的节点、LeetCode19 删除链表的倒数第N个节点、LeetCode160 链表相交、LeetCode142 环形链表Ⅱ

今日任务：

1. 链表理论基础
2. LeetCode203 移除链表元素
3. LeetCode707 设计链表
4. LeetCode206 反转链表



资料来源：

[代码随想录 | LeetCode203 移除链表元素](https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)

[代码随想录 | LeetCode707 设计链表](https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)

[代码随想录 | LeetCode206 反转链表](https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)


### 1 LeetCode203 移除链表元素


:::info{title="题目"}
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
 

示例 1：
```
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
```
示例 2：
```
输入：head = [], val = 1
输出：[]
```
示例 3：
```
输入：head = [7,7,7,7], val = 7
输出：[]
```

提示：

* 列表中的节点数目在范围 [0, 104] 内
* 1 <= Node.val <= 50
* 0 <= val <= 50
:::

一开始没想那么多，直接就遍历然后写了，碰见一个删一个。

``` python
# 我的代码
from typing import Optional

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        point = head
        if head is None:
            return head
        while point.next is not None:
            if point.next.val == val and point.next.next is not None:
                point.next = point.next.next
            elif point.next.val == val and point.next.next is None:
                point.next = None
            elif point.next.val != val:
                point = point.next
        if head.val == val:
            return head.next
        return head
```

写完之后看了文档，才知道虚拟头节点这个技巧。在链表原本的头节点之前加一个虚拟头节点，在针对头节点和尾节点进行处理时比较方便。

``` python
from typing import Optional

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        # 虚拟头节点
        virtual_head = ListNode(next=head)
        point = virtual_head
        while point.next is not None:
            if point.next.val == val:
                point.next = point.next.next
            else:
                point = point.next
        return virtual_head.next
```

### 2 LeetCode707 设计链表

:::info{title="题目"}
你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

* MyLinkedList() 初始化 MyLinkedList 对象。
* int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
* void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
* void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
* void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
* void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。
 

示例：

```
输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]

解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
myLinkedList.get(1);              // 返回 2
myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
myLinkedList.get(1);              // 返回 3
```
 

提示：

* 0 <= index, val <= 1000
* 请不要使用内置的 LinkedList 库。
* 调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 * 2000 。
:::

原本以为很快就能写完的，然后被爆杀。主要原因还是对各个方法主要的要循环的区间和实际要操作的元素不清。

* `get`方法：它能接收的查找`index`就是0到`max_index`，进行循环的区间也是从实际链表的头节点开始即可。
* `addAtHead`方法：它实际要对虚拟头节点进行处理。
* `addAtTail`方法：它实际要对最后一个节点进行处理。
* `addAtIndex`方法：它能接收的查找`index`就是0到`max_index + 1`，但是进行循环的区间是从虚拟头节点开始到最后一个节点。它实际要对`index - 1`处的节点进行处理。
* `deleteAtIndex`方法：它能接收的查找`index`是0到`max_index`，进行进行循环的区间是从虚拟头节点开始到倒数第二个节点。它实际要对`index - 1`处的节点进行处理。

``` python
# 我的代码
class Node:
    def __init__(self, val: int = 0, next: 'Node' = None):
        self.val = val
        self.next = next

class MyLinkedList:

    def __init__(self):
        self.virtual_head = Node()
        self.max_index = -1  # 最大允许的索引


    # def test(self):
    #     print("test")
    #     if self.virtual_head.next is None:
    #         return
    #     point = self.virtual_head.next
    #     while point.next is not None:
    #         print(point.val)
    #         point = point.next
    #     print(point.val)
    #     print("\n", end="")


    def get(self, index: int) -> int:
        # self.test()
        # 判断是否合法
        if index > self.max_index:
            return -1
        point = self.virtual_head.next
        for _ in range(index):
            point = point.next
        return point.val


    def addAtHead(self, val: int) -> None:
        # self.test()
        new_node = Node(val, self.virtual_head.next)
        self.virtual_head.next = new_node
        self.max_index += 1


    def addAtTail(self, val: int) -> None:
        # self.test()
        # 实际要处理的是最后一个节点 point需要指向最后一个节点
        new_node = Node(val, None)
        point = self.virtual_head
        for _ in range(self.max_index + 1):
            point = point.next
        point.next = new_node
        self.max_index += 1


    def addAtIndex(self, index: int, val: int) -> None:
        # self.test()
        # 实际要处理的是index-1位置上的节点 point需要指向这里
        # 判断合法
        if index > self.max_index + 1 or index < 0:  # 因为addAtIndex 也可以在末尾添加 末尾对应的就是max_index + 1
            return
        elif index == 0:
            self.addAtHead(val)
            return
        point = self.virtual_head.next
        for _ in range(index - 1):
            point = point.next
        new_node = Node(val, point.next)
        point.next = new_node
        self.max_index += 1


    def deleteAtIndex(self, index: int) -> None:
        # self.test()
        # 实际要处理的是index-1位置上的节点 point需要指向这里
        # 判断合法
        if index > self.max_index or index < 0:
            return
        point = self.virtual_head  # 这里想清楚deleteAtIndex的要处理的范围 它是可能要处理virtual_head的
        for _ in range(index):
            point = point.next
        if index == self.max_index:
            point.next = None
        else:
            point.next = point.next.next
        self.max_index -= 1
```

再把代码随想录的简洁python代码贴在这：

``` python
（版本一）单链表法
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        
class MyLinkedList:
    def __init__(self):
        self.dummy_head = ListNode()
        self.size = 0

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        
        current = self.dummy_head.next
        for i in range(index):
            current = current.next
            
        return current.val

    def addAtHead(self, val: int) -> None:
        self.dummy_head.next = ListNode(val, self.dummy_head.next)
        self.size += 1

    def addAtTail(self, val: int) -> None:
        current = self.dummy_head
        while current.next:
            current = current.next
        current.next = ListNode(val)
        self.size += 1

    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0 or index > self.size:
            return
        
        current = self.dummy_head
        for i in range(index):
            current = current.next
        current.next = ListNode(val, current.next)
        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        
        current = self.dummy_head
        for i in range(index):
            current = current.next
        current.next = current.next.next
        self.size -= 1
```

### 3 LeetCode206 反转链表


:::info{title="题目"}
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 

示例 1：
```
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
```
示例 2：
```
输入：head = [1,2]
输出：[2,1]
```
示例 3：
```
输入：head = []
输出：[]
```

提示：

* 链表中节点的数目范围是 [0, 5000]
* -5000 <= Node.val <= 5000
:::

一开始想不到思路，只好暴力破解，多开一个链表另存数据。

``` python
# 我的代码
from typing import Optional

# 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]:
        if head is None:
            return None
        new_reverse_list_after = ListNode(head.val)
        while True:
            if head.next is not None:
                head = head.next
                new_reverse_list_before = ListNode(head.val, new_reverse_list_after)
                new_reverse_list_after = new_reverse_list_before
            else:
                break
        return new_reverse_list_after
```

最快解法是运用三个指针来进行元素指向的反转。一次反转过程是这样的：

1. 初始状态下，before指向上一个已经反转完成的节点，after指向准备反转的节点。
2. 使temp指向after的下个节点
3. 使after所指向的节点反转指向before
4. 使before指向after所指向的节点
5. 使after指向temp所指向的节点。

``` python
from typing import Optional

# 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]:
        before = None
        after = head
        while after:
            temp = after.next
            after.next = before
            before = after
            after = temp
        return before
```

另外这个递归也没确实想过，贴在这里。

``` python
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        return self.reverse(head, None)
    def reverse(self, cur: ListNode, pre: ListNode) -> ListNode:
        if cur == None:  # 到尽头了
            return pre
        # 在下面进行反转
        temp = cur.next
        cur.next = pre
        return self.reverse(temp, cur)  # 使下一个节点开始反转 
```

代码随想录算法训练营第三天 | LeetCode203 移除链表元素、LeetCode707 设计链表、LeetCode206 反转链表

今日任务：

1. LeetCode977 有序数组的平方
2. LeetCode209 长度最小的子数组 
3. LeetCode59 螺旋矩阵Ⅱ



> 今日心情：今天一天的课，在椅子上缩着坐了一天，腰好累。

资料来源：

[977.有序数组的平方](https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)

[209.长度最小的子数组](https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)

[59.螺旋矩阵II](https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)

### 1 LeetCode977 有序数组的平方


:::info{title="题目"}

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：
```
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
```
示例 2：
```
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
```

提示：

* 1 <= nums.length <= 104
* -104 <= nums[i] <= 104
* nums 已按 非递减顺序 排序
:::

在一开始看到这道题的时候，我原本是有思路的，想着从数组的两端同时向中间循环，被循环的值进行比较。但是只想着在原数组中进行操作了，想着根据比较的结果交换位置，但是越换越乱，在看了视频之后才如梦初醒。

``` python
from typing import List

# 对于取绝对值和insert函数这种 还是允许我稍微偷个懒吧（）
# 毕竟这里insert起到的作用起到的作用和反向填充数组是一样的
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        first = 0
        last = len(nums) - 1
        return_list = list()
        while first <= last:
            if abs(nums[first]) < abs(nums[last]):
                return_list.insert(0, nums[last] * nums[last])
                last -= 1
            else:
                return_list.insert(0, nums[first] * nums[first])
                first += 1
        return return_list
```

### 2 LeetCode209 长度最小的子数组


:::info{title="题目"}
给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续
子数组
 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

 

示例 1：
```
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
```
示例 2：
```
输入：target = 4, nums = [1,4,4]
输出：1
```
示例 3：
```
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
```

提示：

* 1 <= target <= 109
* 1 <= nums.length <= 105
* 1 <= nums[i] <= 105
:::

在看到窗口之后，大致就知道这题是个什么思路了，只是在最后一轮要根据`left`结束循环的时候，总是数组越界，最后烦不胜烦直接`while True`然后在`left += 1`之后找条件`break`掉。

``` python
from typing import List

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        right, left, summary, return_len = 0, 0, nums[0], float('inf')
        # float('inf')即为python的无穷大
        while True:
            if summary >= target:
                if (left - right + 1) < return_len:
                    return_len = left - right + 1
                summary -= nums[right]
                right += 1
            else:
                left += 1
                if left >= len(nums):
                    break
                summary += nums[left]
        if return_len == float('inf'):
            return 0
        return return_len
```

### 3 LeetCode59 螺旋矩阵Ⅱ


:::info{title="题目"}
给你一个正整数 n ，生成一个包含 1 到 $n^2$ 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：
```
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
```
示例 2：
```
输入：n = 1
输出：[[1]]
```

提示：

* 1 <= n <= 20
:::

简而言之晕晕，晕的地方倒不是说怎么固定每次填充的区间，主要是体现在坐标上的加加减减有点晕。看了代码随想录的文档之后逐渐摸清了思路，然后写出来了。

``` python
from typing import List

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        return_list = list()
        for _ in range(n):
            return_list.append([0] * n)
        count, offset = 1, 1
        x, y = 0, 0  # 竖向是x 横向是y
        for _ in range(int(n / 2)):  # 圈数
            for y in range(y, n - offset):
                return_list[x][y] = count
                count += 1
            y += 1
            for x in range(x, n - offset):
                return_list[x][y] = count
                count += 1
            x += 1
            for y in range(y, offset - 1, -1):
                return_list[x][y] = count
                count += 1
            y -= 1
            for x in range(x, offset - 1, -1):
                return_list[x][y] = count
                count += 1
            y += 1
            offset += 1
        if (n % 2) != 0:
            return_list[int(n / 2)][int(n / 2)] = count
        return return_list
```


:::warning{title="注意"}
1. 在python中，`for i in range(i, j)`可以等效`for(i; i < j; i++)`。
2. `range()`函数并不会自动生成逆序，需要在`step`参数处传入-1。
3. `list`有长度，创建定长`list`可以使用`a = [0] * n`。
:::

代码随想录算法训练营第二天 | LeetCode977 有序数组的平方、LeetCode209 长度最小的子数组、LeetCode59 螺旋矩阵Ⅱ

今日任务：

1. 数组理论基础
2. LeetCode704 二分查找
3. LeetCode27 移除元素



> 今日心情：今天第一天，万事开头难，终于是赶在睡之前写完了。还想写多个语言版本帮助自己熟悉新语言来着，脑子真是太困了。想想明天的满课就心累。最后祝自己能够找到想去的暑期实习吧。

资料来源：

[数组理论基础](https://programmercarl.com/%E6%95%B0%E7%BB%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html)

[704. 二分查找](https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)

[27. 移除元素](https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html)

### 1 数组理论基础

（只补充之前没了解过的部分）

1. 二维数组在内存中的存储方式随语言不同而不同。C++的二维数组和一维数组是一样的，按顺序排列；而Java的二维数组，每个一维数组之间都是不相连的，由最上层的数组存储指向这些一维数组的地址。

（实在不想自己制图了，但是看图理解确实更快😂）
![image.png](https://www.misaka19327.cc/static/img/9df5cf7fcef472877d8ae258dd5280fb.image.png)

### 2 LeetCode704 二分查找

:::info{title="题目"}
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。


示例 1:
```
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
```

示例 2:
```
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
```

提示：

* 你可以假设 nums 中的所有元素是不重复的。
* n 将在 [1, 10000]之间。
* nums 的每个元素都将在 [-9999, 9999]之间。
:::

~~有一说一，我一开始看到这题以为能秒杀的，真的。~~

> 在计算机科学中，二分查找算法（英语：binary search algorithm），也称折半搜索算法（英语：half-interval search algorithm）、对数搜索算法（英语：logarithmic search algorithm），是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

二分查找的重点在于，如何在代码中规定查找的范围。按查找范围划分，分为**左闭右闭区间**和**左闭右开区间**。以下为二分查找代码的框架，出现问号的地方就是要根据区间不同而填充的地方：

``` python
from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        right = 0
        left = ?
        while right ? left:
            middle = int((right + left) / 2)
            if nums[middle] == target:
                return middle
            elif target < nums[middle]:
                left = ?
            elif target > nums[middle]:
                right = ?
        return -1
```

1. 左闭右闭区间

如果在左闭右闭区间进行搜索，那么就**意味着`right`和`left`这两个变量都是要纳入搜索范围**的，所以在修改`right`和`left`的时候，都不应该等于`middle`，因为就是在`middle`不是`target`的情况下，才需要修改`right`和`left`。同理，`while`条件也应该是`right <= left`，因为在左闭右闭区间下，`left = right`是合理的。

``` python
from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        right = 0
        left = len(nums) - 1
        while right <= left:
            middle = int((right + left) / 2)
            if nums[middle] == target:
                return middle
            elif target < nums[middle]:
                left = middle - 1
            elif target > nums[middle]:
                right = middle + 1
        return -1
```

2. 左闭右开区间

根据左闭右闭区间举一反三，如果在左闭右开区间进行搜索，那么就**意味着`right`在搜索范围里，而`left`不在搜索范围里**，所以在修改`right`和`left`的时候，`right`不应该等于`middle`，而`left`可以。同理，`while`条件也应该是`right < left`，因为在左闭右开区间下，`left = right`是不合理的。

``` python
from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        right = 0
        left = len(nums)
        while right < left:
            middle = int((right + left) / 2)
            if nums[middle] == target:
                return middle
            elif target < nums[middle]:
                left = middle
            elif target > nums[middle]:
                right = middle + 1
        return -1
```

### 3 LeetCode27 移除元素


:::info{title="题目"}
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。


说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

```
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
```

示例 1：
```
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
```
示例 2：
```
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,3,0,4]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
```

提示：

* 0 <= nums.length <= 100
* 0 <= nums[i] <= 50
* 0 <= val <= 100
:::

第一次做直接过了，做的时候想着想着才意识到这何尝不是另一种双指针法，然后看了之后才发现真的双指针法确实方便多了（。

``` python
from typing import List

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        first = 0
        length = len(nums)
        if length == 0:
            return 0
        last = length - 1
        while first <= last:
            if nums[first] == val and nums[last] != val:
                nums[first] = nums[last]
                length -= 1
                first += 1
                last -= 1
            elif nums[first] != val:
                first += 1
            elif nums[first] == val and nums[last] == val:
                last -= 1
                length -= 1
        if first == 0:
            nums.clear()
        return length
```

双指针法：两个指针一起在数组中循环，由快指针寻找不是`val`的值，找到之后就存到慢指针处，然后两个指针一起+1；如果找到的是和`val`相等的值，那么快指针+1，慢指针不动即可。最后循环完成，返回慢指针的位置即可。

``` python
from typing import List

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        fast = 0
        low = 0
        while fast < len(nums):
            if nums[fast] != val:
                nums[low] = nums[fast]
                low += 1
            fast += 1
        return low
```