206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

解题思路:迭代法模板

链表反转的口诀

  1. 保存前进方向
  2. 斩断过去,不忘前事
  3. 继续前行

参考：

  1. //迭代法，时间O(n)，空间O(1)
  2. func reverseList(head *ListNode) *ListNode {    //定义链表函数的方法要记住，返回值也是链表
  3.     var prev *ListNode                //创造 后指针的位置为链表的空节点
  4.     cur := head                        //头结点指针
  6.     for cur != nil {
  7.         temp := cur.Next  //保存下一跳地址，不然无法前进
  8.         cur.Next = prev      //删掉原来的下一跳，转换为翻转跳
  9.         prev = cur        //前驱指针转换完成，更新前进，注意不能用：=赋值，原来有值不用创造
  10.         cur = temp        //继续前进，前指针cur    （左右斜对称！）
  11.     }
  12.     return prev            
  13.     //返回后指针为最后节点（层层包含，能推出整个链表），前指针指向原来的空节点（不要了）
  14. }

解题思路:递归法模板
思路：
一，递归逻辑是将当前链表分为两部分，1.头结点和2.剩余链表
接下来的逻辑为将2.剩余链表反转，然后将1.头结点放到最后就可以了
二，剩余链表的反转和当前的反转逻辑一样，所以可以递归调用。
三，递归的终止条件就是链表的最后一个节点是直接返回最后的那个节点，判断条件为node.Next == nil

//递归法 时间On,空间On
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {  
        return head          //主要是后一种，递归到头了
    }

    res := reverseList(head.Next)    //以head.next为头结点的链表，进行反转，res反转后链表
                                     //把前面的打包，和最后的一位对比，递归通项公式，里面两行相当于是包含for 反复调用

    head.Next.Next = head            //先反转链表，下一跳head.next的指针指向自己
    head.Next = nil                  //自己的指为空节点，保证自己是最后时，指向空,防止成环（两个元素时）
    return res                       //直接返回res 相当于新定义的链表【】，所以占内存
}