反转链表

https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/solution/shi-pin-jiang-jie-die-dai-he-di-gui-hen-w2gm0/

方法一：递归
递归法遍历链表，当越过尾节点后终止递归，在回溯时修改各节点的 next 引用指向。recur(cur, pre) 递归函数.

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


def reverseList(self, head: ListNode) -> ListNode:
    if head is None or head.next is None:
        return head
    
    p = self.reverseList(head.next)
    head.next.next = head
    head.next = None

    return p


// 递归go
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    var p = reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return p
}

方法二：迭代（双指针）
遍历链表，并在访问各节点时修改 next 引用指向

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur, pre = head, None
        while cur:
            tmp = cur.next # 暂存后继节点 cur.next
            cur.next = pre # 修改 next 引用指向
            pre = cur      # pre 暂存 cur
            cur = tmp      # cur 访问下一节点
        return pre

// 迭代go
func reverseList1(head *ListNode) *ListNode {
    var prev *ListNode = nil
    var curr = head
    for curr != nil {
        var next = curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }
    return prev
}