反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

type ListNode struct {
	Val  int
	Next *ListNode
}

递归解法

func reverseList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	//1->2->3->4->5->nil
	//根据上面的递归终止条件，这里第一次返回的时候，返回的是最后一个节点
	//也就是cur = 5, head = 4, head.Next = 5
	cur := reverseList(head.Next)
	//head.Next = 5, 5.Next = head(4)
	//这样子就完成了5->4, 同时原本的4->5
	head.Next.Next = head
	//将4->5变成4->nil
	head.Next = nil
	
	//这里的cur就永远是最后一个了，相当于新链表的头
	return cur
}

非递归解法

func reverseList(head *ListNode) *ListNode {
	var (
		prev *ListNode
		tmp  *ListNode
		cur  = head
	)

	for cur != nil {
        //保存当前的下一个
		tmp = cur.Next
        //当前指向前一个
		cur.Next = prev
        //当前给前一个
		prev = cur
        //取出下一个
		cur = tmp
	}
	return prev
}