今日任务：

1. LeetCode454 四数相加 Ⅱ
2. LeetCode383 赎金信
3. LeetCode15 三数之和
4. LeetCode18 四数之和



> ~~今日~~心情：终于找机会补回来了。

资料来源：

1. [代码随想录 | LeetCode454 四数相加 Ⅱ](https://programmercarl.com/0454.%E5%9B%9B%E6%95%B0%E7%9B%B8%E5%8A%A0II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
2. [代码随想录 | LeetCode383 赎金信](https://programmercarl.com/0383.%E8%B5%8E%E9%87%91%E4%BF%A1.html)
3. [代码随想录 | LeetCode15 三数之和](https://programmercarl.com/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
4. [代码随想录 | LeetCode18 四数之和](https://programmercarl.com/0018.%E5%9B%9B%E6%95%B0%E4%B9%8B%E5%92%8C.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)

### 1 LeetCode454 四数相加 Ⅱ

:::info{title="题目"}
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
 

示例 1：
```
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
```
示例 2：
```
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1
```

  提示：

- n == nums1.length
- n == nums2.length
- n == nums3.length
- n == nums4.length
- 1 <= n <= 200
- -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

:::

四个元组分成两组，一组确定需要什么数字，另一组去匹配这个数字，这个过程就需要哈希表。注意这里只是查有多少，而不是具体把它们都找出来。

``` python
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        test_dict = {}
        for i in nums1:
            for j in nums2:
                if i + j in test_dict.keys():
                    test_dict[i + j] += 1
                else:
                    test_dict[i + j] = 1
        count = 0
        for i in nums3:
            for j in nums4:
                if -(i + j) in test_dict.keys():
                    count += test_dict[-(i + j)]
        return count
```

### 2 LeetCode383 赎金信

:::info{title="题目"}
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

 

示例 1：
```
输入：ransomNote = "a", magazine = "b"
输出：false
```
示例 2：
```
输入：ransomNote = "aa", magazine = "ab"
输出：false
```
示例 3：
```
输入：ransomNote = "aa", magazine = "aab"
输出：true
```

提示：

- 1 <= ransomNote.length, magazine.length <= 105
- ransomNote 和 magazine 由小写英文字母组成
:::

两个字符匹配嘛，这个哈希表最擅长了，键存字符，值存数字。

``` python
class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        test_dict = {}
        for i in magazine:
            if i in test_dict:
                test_dict[i] += 1
            else:
                test_dict[i] = 1
        for i in ransomNote:
            if i not in test_dict:
                return False
            elif test_dict[i] == 0:
                return False
            else:
                test_dict[i] -= 1
        return True
```

### 3 LeetCode15 三数之和

> 内心OS：不愧是梦破碎的地方。

:::info{title="题目"}
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

 

示例 1：
```
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
```
示例 2：
```
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
```
示例 3：
```
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
```

提示：

- 3 <= nums.length <= 3000
- -105 <= nums[i] <= 105
:::

如果只是找哪三个数的和是0的话，还不至于被称为“梦破碎的地方”。主要是这个去重得好好想一下。去重使得使用哈希表来解成本太高了，还是双指针好一些。

先对这个数组进行排序，然后循环，每次循环设置从这次循环的位置到结尾的双指针，两个指针指向的数字再加一个循环的数字加起来验证是不是0。如果是0就存起来，如果大于0则移动右指针，如果小于0则移动左指针。

去重分为两个部分，一个部分是针对循环的，如果这次循环的数字和上次一致，就没有必要再双指针找了，因为只会找出一模一样的组合；另一个部分是针对发现三数组合存起来之后，两个指针必须要移动到和之前指的数字不同的位置，否则还是一模一样的组合。

还有两点，一个是判断大于0或者小于0之后没有必要再查重了，既然已经判断相加不能为0了，那左右都是移动，在`while right < left`里慢慢移动就好；另一个是我没写的，在对数组进行排序之后可以直接判断，如果数组开头就大于0的话就没有必要看了，最小的数都是正数还怎么加起来等于0。

:::warning{title="注意"}
我写的代码把right和left写反了，right实际上是左侧指针，left实际上是右侧指针。
:::

``` python
from typing import List

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        nums.sort()

        for i in range(len(nums) - 1):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            right = i + 1
            left = len(nums) - 1
            while right < left:
                if nums[i] + nums[right] + nums[left] == 0:
                    result.append([nums[i], nums[right], nums[left]])
                    # 只有在这里才有对left和right去重的意义
                    while right < left and nums[right] == nums[right + 1]:
                        right += 1
                    while right < left and nums[left] == nums[left - 1]:
                        left -= 1
                    right += 1
                    left -= 1
                elif nums[i] + nums[right] + nums[left] > 0:
                    left -= 1
                elif nums[i] + nums[right] + nums[left] < 0:
                    right += 1

        return result
```       

### 4 LeetCode18 四数之和

:::info{title="题目"}
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。

示例 1：
```
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
```
示例 2：
```
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
```

提示：

- 1 <= nums.length <= 200
- -109 <= nums[i] <= 109
- -109 <= target <= 109
:::

这题思路和上一题是一样的，只是多了一层循环，也要考虑一开始的剪枝条件的变化和对第二层循环的处理。

``` python
from typing import List

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        result = []
        # 新的剪枝条件 不能再判断数组第一个元素大于或小于target了
        if target < 0 < nums[0]:
            return result
        if nums[len(nums) - 1] < 0 < target:
            return result

        for i in range(len(nums) - 1):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            # 注意是从i + 1开始循环
            for j in range(i + 1, len(nums) - 1):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                left = j + 1
                right = len(nums) - 1
                while left < right:
                    if nums[i] + nums[j] + nums[left] + nums[right] == target:
                        result.append([nums[i], nums[j], nums[left], nums[right]])
                        while left < right and nums[left] == nums[left + 1]:
                            left += 1
                        while left < right and nums[right] == nums[right - 1]:
                            right -= 1
                        left += 1
                        right -= 1
                    elif nums[i] + nums[j] + nums[left] + nums[right] < target:
                        left += 1
                    else:
                        right -= 1

        return result
```

代码随想录算法训练营第七天 | LeetCode454 四数相加 Ⅱ、LeetCode383 赎金信、LeetCode15 三数之和、LeetCode18 四数之和

### 1 配置Nginx Proxy Manager并启动

随便哪里新建一个文件夹，在文件夹下新建`docker-compose.yml`配置文件，并且编辑文件：

```
version: '3'
services:
  app:
    image: 'jc21/nginx-proxy-manager:latest'
    restart: unless-stopped
    ports:
      - '80:80'              # 不建议修改端口
      - '81:81'              # 可以把冒号左边的 81 端口修改成你服务器上没有被占用的端口
      - '443:443'            # 不建议修改端口
    volumes:
      - ./data:/data         # 点号表示当前文件夹，冒号左边的意思是在当前文件夹下创建一个 data 目录，用于存放数据，如果不存在的话，会自动创建
      - ./letsencrypt:/etc/letsencrypt  # 点号表示当前文件夹，冒号左边的意思是在当前文件夹下创建一个 letsencrypt 目录，用于存放证书，如果不存在的话，会自动创建
```

之后在这个文件夹所在位置启动终端，输入以下命令以启动Nginx Proxy Manager：

```
docker-compose up -d     # -d 表示后台运行
```

之后访问81端口（我的镜像是19327端口）即可打开Nginx Proxy Manager的页面。

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

### 2 配置Halo并启动

和配置Nginx Proxy Manager一个步骤：

``` 
version: "3"

services:
  halo:
    image: halohub/halo:2.13
    container_name: halo
    restart: on-failure:3
    depends_on:
      halodb:
        condition: service_healthy
    networks:
      halo_network:
    volumes:
      - ./halo2:/root/.halo2
    ports:
      - "8090:8090"
    healthcheck:
      test: ["CMD", "curl", "-f", "http://localhost:8090/actuator/health/readiness"]
      interval: 30s
      timeout: 5s
      retries: 5
      start_period: 30s
    command:
      - --spring.r2dbc.url=r2dbc:pool:mysql://halodb:3306/halo
      - --spring.r2dbc.username=root
      # MySQL 的密码，请保证与下方 MYSQL_ROOT_PASSWORD 的变量值一致。
      - --spring.r2dbc.password=o#DwN&JSa56
      - --spring.sql.init.platform=mysql
      # 外部访问地址，请根据实际需要修改
      - --halo.external-url=http://localhost:8090/

  halodb:
    image: mysql:8.1.0
    container_name: halodb
    restart: on-failure:3
    networks:
      halo_network:
    command: 
      - --default-authentication-plugin=caching_sha2_password
      - --character-set-server=utf8mb4
      - --collation-server=utf8mb4_general_ci
      - --explicit_defaults_for_timestamp=true
    volumes:
      - ./mysql:/var/lib/mysql
      - ./mysqlBackup:/data/mysqlBackup
    ports:
      - "3306:3306"
    healthcheck:
      test: ["CMD", "mysqladmin", "ping", "-h", "127.0.0.1", "--silent"]
      interval: 3s
      retries: 5
      start_period: 30s
    environment:
      # 请修改此密码，并对应修改上方 Halo 服务的 SPRING_R2DBC_PASSWORD 变量值
      - MYSQL_ROOT_PASSWORD=o#DwN&JSa56
      - MYSQL_DATABASE=halo

networks:
  halo_network:
```

```
docker-compose up -d
docker-compose logs -f // 查看实时日志
```

### 3 Nginx Proxy Manager配置反向代理

先把CloudFlare的CDN加速关掉。

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

如果使用了docker容器，则使用`ip addr show docker0`查看在容器里的IP。

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

如图，Domain Name写域名，Scheme是协议不用管，Forward HostName/IP写127.0.0.1或者写刚才看的在docker容器里的IP，Forward Port写运行的服务所占用的端口（Halo默认8090）。Cache Assets是缓存，Block Common Exploits是阻止常见漏洞，Websockets Support是WebSocket接口支持，都可以打开。Access List是访问控制列表，不用管。

如果想要https访问（前提是域名已经解析到Nginx Proxy Manager所在的机器IP上），看下图：

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

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

选中Force SSL，其他四个不用管，点Save，理论上就申请好了。

最终配置完成应该长这样：

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

配置Halo相关信息

今日任务：

1. 哈希表理论基础
2. LeetCode242 有效的字母异位词
3. LeetCode349 两个数组的交集
4. LeetCode202 快乐数
5. LeetCode1 两数之和



资料来源：

1. [代码随想录 | 哈希表理论基础](https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E5%93%88%E5%B8%8C%E8%A1%A8)
2. [代码随想录 | LeetCode242 有效的字母异位词](https://programmercarl.com/0242.%E6%9C%89%E6%95%88%E7%9A%84%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
3. [代码随想录 | LeetCode349 两个数组的交集](https://programmercarl.com/0349.%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
4. [代码随想录 | LeetCode202 快乐数](https://programmercarl.com/0202.%E5%BF%AB%E4%B9%90%E6%95%B0.html#%E6%80%9D%E8%B7%AF)
5. [代码随想录 | LeetCode1 两数之和](https://programmercarl.com/0001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)

### 1 哈希表理论基础

#### 1.1 `dict`的底层原理

python3.5版本及之前的所有版本里，`dict`的底层是由二维数组构成的，每个数组中存放的是键的哈希值，键和值。每次取值时，先求出键的哈希值，然后取余得到数组下标，从而得到键所对应的值。其在内存中大体是这样的：

``` python
my_dict['name'] = 'jkc'
 
'''
此时的内存示意图
[
  [---, ---, ---],
  [---, ---, ---],
  [---, ---, ---],
  [---, ---, ---],
  [---, ---, ---],
  [1278649844881305901, 指向name的指针, 指向jkc的指针],
  [---, ---, ---],
  [---, ---, ---]
]
'''
```

:::tip{title="提示"}
python的哈希函数`hash()`和常规的哈希函数不太一样，它的哈希函数只能保证一个值在每个运行时内所对应的哈希值是相同的。一旦不在一个运行时里，得到的哈希值就可能不同。

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

这种存储方式也会带来一些弊端，比如说遍历字典的结果顺序不一定就是添加顺序，因为遍历字典本质上还是遍历那个二维数组而已，而那个二维数组的顺序只取决于键的哈希值。

在python3.6版本之后，字典的底层由一个二维数组和一个一维数组组成。每次在存入值时，还是先对键取哈希值然后取余，之后取余的结果对应一维数组的位置，一维数组中存储着这个键值对在二维数组中的位置，二维数组中存储键的哈希值，键和值。其在内存中大概是这样的：

``` python
my_dict['name'] = 'jkc'
my_dict['address'] = 'xxx'
my_dict['salary'] = 999999
 
'''
此时的内存示意图
indices = [1, 0, None, None, None, None, 2, None]
 
entries = [
  [-5954193068542476671, 指向name的指针, 执行jkc的指针],
  [9043074951938101872, 指向address的指针，指向xxx的指针],
  [7324055671294268046, 指向salary的指针, 指向999999的指针]
]
'''
```

这样就避免了之前版本中加元素顺序和遍历顺序不同的问题，并且空间上可以小很多，因为之前的版本的字典必须生成足够大的二维数组来存储键值对（即在之前的版本，即使只是初始化字典，也已经有了8\*3大小的二维数组）。

来源：[python进阶（24）Python字典的底层原理以及字典效率](https://www.cnblogs.com/jiakecong/p/15881370.html)

#### 1.2 `set`的底层原理

python的集合的底层是由哈希表构成的。向一个集合中插入元素的过程，就是向哈希表插入元素的过程。只是如果插入的位置已经有元素的话，python会比较它们俩的值（`__eq__()`）和哈希值（`__hash__()`）来确定它们是否一致，一致就是重复元素，不一致就是哈希碰撞。同理，查找元素时如果哈希值对应的位置有值，先比较值，值不同的话就是哈希碰撞。删除元素时，python也会按照这个顺序找元素，找到之后会赋一个特殊的值，等到下次集合调整大小时再删除。

#### 1.3 `dict`和`set`的操作

1. `dict`
- 初始化：`a = {}`或`a = dict()`
- 添加或修改元素：`a[i] = j`
- 删除并且返回被删除键对应的值：`a.pop(i)`
- 访问元素，如果键不存在则返回默认值：`a.get(key, defaultValue)`
- 清空字典：`a.clear()`
- 以列表形式返回可遍历的(key, value)元组类型数组：`a.items()`（具有类似效果的，但是只返回键或值的：`a.keys()``a.values()`）
2. `set`
- 初始化：`a = set()`
- 添加元素：`a.add(i)`
- 删除元素：`a.discard(i)`（该方法在i不存在于a时不会报错，会报错的版本是`a.delete(i)`）
- 清空集合：`a.clear()`

### 2 LeetCode242 有效的字母异位词

:::info{title="题目"}
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:
```
输入: s = "anagram", t = "nagaram"
输出: true
```
示例 2:
```
输入: s = "rat", t = "car"
输出: false
```

提示:

* 1 <= s.length, t.length <= 5 * 104
* s 和 t 仅包含小写字母
:::

``` python
# 我的代码
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        s_map = {}
        t_map = {}
        for i in s:
            if i in s_map:
                s_map[i] += 1
            else:
                s_map[i] = 1
        for i in t:
            if i in t_map:
                t_map[i] += 1
            else:
                t_map[i] = 1
        if len(s_map) < len(t_map):
            temp = s_map
            s_map = t_map
            t_map = temp
        for char, num in s_map.items():
            if char not in t_map:
                return False
            else:
                if t_map[char] != num:
                    return False
        return True
``` 

这里直接用数组就好，因为说到底要查的东西总共就26种，没必要上哈希表了。

``` python
# 使用更少内存的一种写法
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        record = [0] * 26
        for i in s:
            record[ord(i) - ord('a')] += 1
        for i in t:
            record[ord(i) - ord('a')] -= 1
        for i in record:
            if i != 0:
                return False
        return True
```

### 3 LeetCode349 两个数组的交集

:::info{title="题目"}
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：
```
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
```
示例 2：
```
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
```

提示：

* 1 <= nums1.length, nums2.length <= 1000
* 0 <= nums1[i], nums2[i] <= 1000
:::

先用`set`去重，然后再和另一个数组进行比较，比较的结果就是交集了。

``` python
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        set_nums1 = set()
        return_list = []
        for i in nums1:
            set_nums1.add(i)
        for i in nums2:
            if i in set_nums1:
                return_list.append(i)
                set_nums1.discard(i)
        return return_list
```

### 4 LeetCode202 快乐数

:::info{title="题目"}
编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：
```
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
```
示例 2：
```
输入：n = 2
输出：false
```

提示：

* 1 <= n <= 231 - 1
:::

一定要注意，**当遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法**。这题就是用`set`去暴力解。

``` python
class Solution:
    def isHappy(self, n: int) -> bool:
        test_set = set()
        sum = n
        while True:
            n_str = str(sum)
            sum = 0
            for i in n_str:
                sum += int(i) * int(i)
            if sum == 1:
                return True
            if sum in test_set:
                return False
            else:
                test_set.add(sum)
```          

### 5 LeetCode1 两数之和

:::info{title="题目"}
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

 

示例 1：
```
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
```
示例 2：
```
输入：nums = [3,2,4], target = 6
输出：[1,2]
```
示例 3：
```
输入：nums = [3,3], target = 6
输出：[0,1]
```

提示：

* 2 <= nums.length <= 104
* -109 <= nums[i] <= 109
* -109 <= target <= 109
* 只会存在一个有效答案
:::

主要是想明白这个`map`要存的是谁，要找的是谁。

``` python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        test_map = {}
        for i in range(len(nums)):
            if (target - nums[i]) not in test_map.keys():
                test_map[nums[i]] = i
            else:
                return [i, test_map[target - nums[i]]]
```

代码随想录算法训练营第六天 | LeetCode242 有效的字母异位词、LeetCode349 两个数组的交集、LeetCode202 快乐数、LeetCode1 两数之和

今日任务

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)  # 使下一个节点开始反转 
```