翻转链表
最后更新于：2022-04-02 04:22:17
[TOC]
## 翻转链表
### 递归
go 示例:
```
func reverse(head *Node) *Node {
if head.next == nil {
return head
}
last := reverse(head.next)
// 翻转链接
// 如 1->2->3->4->5,把1->2->3->4->5->4
// 既把 4的next的next指向head 4的next为5
// 既把 5的next 指向4
head.next.next = head
// 断掉链表:如把原来的4->5 断掉
head.next = nil
return last
}
```
图示:
### 迭代
go 示例
```
func reverse2(head *Node) *Node {
// newHead 为新链表,元素向前追加
var newHead *Node
tmp := head
// head 标识将要被添加的元素
for tmp != nil {
// tmp 指向 head.next
tmp = head.next
// 把最开始的节点指向新节点
// 相当于向前添加一个元素
head.next = newHead
// newHead 更新头,指向新的头
newHead = head
// head 指向下一个节点
head = tmp
}
return newHead
}
```
图示:
## 反转链表前 N 个节点
```
var succer *Node
func reverseN(head *Node, n int) *Node {
if n == 1 {
//base case 变为 n == 1，反转一个元素，就是它本身，同时要记录后驱节点
succer = head.next
return head
}
n--
last := reverse(head.next, n)
head.next.next = head
head.next = succer
return last
}
```
1. 与全部翻转不同的是,部分翻转,需要将翻转的最后一个值指向未翻转的第一个元素
2. base case 需要记录最后一个翻转的值,返回凭借
如翻转3个,那么 succer 为3后面的元素 4,然后把head指向4
';