[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