反转链表的两种方法

1. 迭代

遍历链表，存储下一个节点，将当前节点的 next 指针指向前一个节点，并将当前节点存储为上一个节点，将下一个节点存储为当前节点。

func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    var prev, cur, next *ListNode
    cur = head
    for cur != nil {
        next = cur.Next
        cur.Next, prev = prev, cur
        cur = next
    }
    return prev
}

2. 递归

递归遍历链表，将当前节点的下一个节点的next指针指向当前节点，当前节点的next指针指向空。
假设链表结构为1->2->NULL，则上述操作的结果为节点1的下一个节点(即节点2)的next指针指向节点1（2->1），而节点1的next指针指向NULL（1->2），最终得到的结果是2->1->NULL。

func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    node := reverseList(head.Next)
    head.Next.Next, head.Next = head, nil
    return node
}