反转链表

反转链表是一道有关链表的训练题，虽然比较简单，但是比较能训练思维。反转链表的题目比较自然的思维是用迭代，比较容易实现。但是回忆SICP第一章，凡是用递归可以完成的算法都可以用迭代完成，那么反过来，用递归完成的也应该能够用递归完成。但是这道题递归的做法不容易想清楚。

迭代实现

func reverseList_iteration(head *ListNode) *ListNode {
    setinal := NewListNode(-1)
    for head != nil {
        cur := head
        head = head.Next
        cur.Next = setinal.Next
        setinal.Next = cur
    }
    return setinal.Next
}

迭代的思路是遍历链表，每遍历到一个节点，将该节点插入到结果的头部，直至完成遍历。这里使用了哨兵简化了思路，更加直接。

递归实现

递归实现，直接按照递归思考实际上不太容易思考，直到看到回溯的做法，这个做法简洁明了

func reverseList(head *ListNode) *ListNode {
    return reverseList_recursion(head, nil)
}

func reverseList_recursion(head *ListNode, newHead *ListNode) *ListNode{
    if head == nil {
        return newHead
    }
    next := head.Next
    head.Next = newHead
    return reverseList_recursion(next, head)
}

遍历结束的条件就是head为空。 head存放的是还没有reverse的链表数据，newhead中存放的是已经reverse的数据，每次遍历的时候，取head的第一个节点，放在newHead的头部，然后用head的next继续下一次递归。

小结

链表反转虽然简单，但是确实很考验思维，我训练了三次，对于递归的时候，每次都感觉有点绕，看到回溯后，才觉得恍然大悟。

在实际工程应用中，尽量用选代取代递归，递归要额外消耗栈空间，当递归层次较深，栈将被耗尽，程序漰溃。而有些时候，对于某些语言支持尾递归优化的，在用递归表达清晰的时候，尽量还是用递归，以简洁易懂符合思维习惯。