Algorithm-List
date
Oct 26, 2023
slug
algorithm-list
status
Published
tags
algorithm
type
Post
https://twitter.com/tangdahe
summary
list opt
203 移除链表元素
需要注意，如果头节点也需要删除的话，就需要事先弄一个虚拟头节点
707 设计链表
这道题目设计链表的五个接口：
- 获取链表第index个节点的数值
- 在链表的最前面插入一个节点
- 在链表的最后面插入一个节点
- 在链表第index个节点前面插入一个节点
- 删除链表的第index个节点
可以说这五个接口，已经覆盖了链表的常见操作，是练习链表操作非常好的一道题目
206 反转链表
双指针解法
首先定义一个 curr 指针，指向头结点，再定义一个 prev 指针，初始化为 null。
然后就要开始反转了，首先要把 curr->next 节点用 tmp 指针保存一下，也就是保存一下这个节点。
为什么要保存一下这个节点呢，因为接下来要改变 curr->next 的指向了，将 curr->next 指向 prev，此时已经反转了第一个节点了。
接下来，就是循环走如下代码逻辑了，继续移动 prev 和 curr 指针。
最后，curr 指针已经指向了 null，循环结束，链表也反转完毕了。 此时我们 return prev 指针就可以了，prev 指针就指向了新的头结点。
递归解法
递归到最后一个节点，先反转最后一个
图示逻辑
92 反转链表2
给你单链表的头指针
head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表和上述题目不同，该题需要反转指定 idx 区间的链表。
思路：
- 首先减少 left 边界到 1，即新的 new head，之前的链表不动
- 从 left 开始进行反转，需要进行计数，每反转一次，即递归一次 right - -
- 需要保留
right.next，因为反转结束left.next = right.next
- 反转之后
noChange.next = right
