[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