Section one: 反转链表
出题
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
思路一： 递归法
递归是能想到的最简单明了的方法，对链表的next进行递归操作，既然next经过递归已经是处理好的反向链表，那么我们只用处理当前节点和递归回来的已经反向处理好的节点关系即可。
先看代码：
func reverseList(_ head: ListNode?) -> ListNode? {
if head == nil || head?.next == nil {
return head
}
// 递归过来的节点
let newHeader = reverseList(head!.next)
// 重点是newHeader是最后一个节点，它是反转后的第一个节点
// 我们要获取的是当前节点的下一个节点，就是newHeader的最后一个节点
// 那么就通过head获取
head?.next?.next = head
head?.next = nil
return newHeader
}
newHeader就是上一轮递归完成后的已经反转的链表的头节点，也就是原链表的最后一个节点。而我们要处理的是与当前节点相邻的节点，即newHeader的最后一个节点。
创建一个包含节点1，2，3，4，5的链表为例：
当我们处理最后一次递归的时候，就是处理1节点的时候，此时：
1节点就是header，而newHeader却是指向5，所需要的操作是将1放在2的next，通过newHeader一步一步next拿到2节点显然不是最好的选择。
另一方面，1的next还是2，还没有被断开，所以通过header.next就可以获取2。即 head?.next?.next = head 就是2.next = head，此时就完成了该轮递归的主要操作，但是1的next还是指向2，所有需要将1的next置位空，留作下一轮递归使用（如果有的话）。
思路二： 迭代法
迭代法的思路是一个一个的取出节点，然后再一个一个的放到一个空的链表里边。
仍然以包含节点1，2，3，4，5的链表为例：
处理某一个节点(currentNode)的时候，用nextNode保存这个节点的next。
因为currentNode是一直需要被修改指向进行处理的，所以需要另外一个链头来保存处理好的节点。
又因为新处理好的节点应该放在保存好的节点的前边，即 currentNode?.next = preNode。
到下一轮的时候，preNode应该带有已经处理好的currentNode，即1这个元素。
所以应该将preNode指向当前的currentNode：
然后向后移动currentNode，进行下一轮。
先看代码：
func reverseList(_ head: ListNode?) -> ListNode? {
if head == nil || head?.next == nil {
return head
}
// 返回节点
var preNode: ListNode?
// 待迭代的第一个节点
var currentNode = head
while currentNode != nil {
// 保留迭代节点的next，防止丢失
// 保留完next，就可以取出当前的cur放到pre里边
let nextNode = currentNode?.next
// 由于是反向，就是将节点取出来放在pre的前边
currentNode?.next = preNode
preNode = currentNode
// cur置位next，进行下一轮
currentNode = nextNode
}
return preNode
}
由于上轮的preNode是空元素，继续走一轮，配合代码一起查看。
此时经过第一轮，preNode保存了1节点，currentNode走到2节点，先将currentNode的next保存：
然后将currentNode的next指向上次保存好的节点（preNode）:
然后更新preNode留作下次使用。形成值为2->1的链表：
此就完成了本轮的任务，继续更新currentNode进行下一轮即可。
思路三： 栈辅助
遵循栈元素先进后出的规则，也由于需要将所有节点入栈拿到栈顶节点一个一个出栈。所以免不了两次遍历，代码如下：
func reverseList(_ head: ListNode?) -> ListNode? {
if head == nil || head?.next == nil {
return head
}
var stack: [ListNode] = []
var fhead = head
while fhead != nil {
stack.append(fhead!)
fhead = fhead?.next
}
let preNode: ListNode? = stack.popLast()
// 指向preNode， 因为是类，所以处理next 等于处理pre
var nextNode: ListNode? = preNode
// 栈不为空
while !stack.isEmpty {
// 继续取节点
let node = stack.popLast()
// 将上次记录的节点的next 指向刚取出的next
nextNode?.next = node
// 移动next到下一节点
nextNode = node
}
// 将最后一个节点的next清空，避免造成链循环
nextNode?.next = nil
return preNode
}
Section two: 反转链表的部分数据
出题
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
思路一： 递归法
显然，递归法的思路还是最容易思考的，例如我们只用将区间的链表取出来，递归后拼接到原链表上，就可以完成此操作了。但是另一方面，这个实现明显是困难的，在递归中操作需要外置内存保存此取出来的链表，还需要保存左右边界节点。那么该如何操作呢？
不妨将此问题拆解开来，先探讨下如何求链表从头开始到right个元素的反转链表。
即假设有一个包含节点1，2，3，4，5的链表为例，如果right = 3，那么得到的链表应该是 3、2、1、4、5。即反转right个节点。
在这个问题中，需要考虑两个重点：
- 计数问题：在不引用外部变量的状况下，如何获取当前是right=3范围内的节点是需要思考的内容。在递归中，可以传入right-1的值作为递归参数，由于计数并非从0开始，所以当right = 1时，即为最后边界。
- 边界后的节点问题：因为要跨出递归保存，所以依然需要外部变量支持，才能得以 保存。
代码如下：
// 保存后面的节点
var endNode: ListNode?
func reverseSectionLength(_ head: ListNode?, _ right: Int) -> ListNode? {
if right == 1 {
// 到达边界， 保存边界后的节点
endNode = head?.next
// 返回边界内的最后一个节点
return head
}
// 递归返回的节点
var lastNode = reverseSectionLength(head?.next, right - 1)
// 边界前的需要反转的节点依旧进行反转
head?.next?.next = head
// 本来需要置位空，但现在right后边的节点需要追加到反转完成链表后边
head?.next = endNode
return lastNode
}
至此，完成了前right个元素的反转操作，由于是从第1个元素开始的，所以可以认为是从1到right的区间，回到原来的问题，如何获取 left到right的反转区间呢？
可以片面的认为：
func reverseBetween(_ head: ListNode?, _ left: Int, _ right: Int) -> ListNode? {
if head == nil || head?.next == nil {
return head
}
if left == 1 {
return reverseSectionLength(head, right)
}
。。。
}
如果我们把 head 的索引视为 1，那么我们是想从第 left 个元素开始反转对吧；如果把 head.next 的索引视为 1 呢？反正前边的节点也不反转嘛！ 那么相对于 head.next，反转的区间应该是从第 left - 1 个元素开始的；那么对于 head.next.next 呢……
所以完整的代码为：
var endNode: ListNode?
func reverseSectionLength(_ head: ListNode?, _ right: Int) -> ListNode? {
if right == 1 {
// 到达边界， 保存边界后的节点
endNode = head?.next
// 返回边界内的最后一个节点
return head
}
// 递归返回的节点
let lastNode = reverseSectionLength(head?.next, right - 1)
head?.next?.next = head
// 本来需要置位空，但现在right后边的节点需要追加到反转完成链表后边
head?.next = endNode
return lastNode
}
func reverseBetween(_ head: ListNode?, _ left: Int, _ right: Int) -> ListNode? {
if head == nil || head?.next == nil {
return head
}
if left == 1 {
return reverseSectionLength(head, right)
}
head?.next = reverseBetween(head?.next, left - 1, right - 1)
return head
}
思路二： 迭代法
代码如下：
func reverseBetween(_ head: ListNode?, _ left: Int, _ right: Int) -> ListNode? {
guard left <= right || head != nil else {
return nil
}
let dummy: ListNode? = ListNode(0)
dummy?.next = head
var prev = dummy
for _ in 0 ..< left - 1 {
prev = prev?.next
}
let cur = prev?.next
for _ in left ..< right { //重点逻辑是： 找到前面的一个节点。之后的 left到right之际两两反转
let next = cur?.next
cur?.next = next?.next
next?.next = prev?.next
prev?.next = next
}
return dummy?.next
}
与反转整个链表相似，重点逻辑， 找到前面的一个节点。之后的 left到right之际两两反转。
