Reverse Linked List

题目介绍

LeetCode 206. Reverse Linked List，反转链表，迭代法和递归法同时实现。

解题思路

算法学习 - 链表 对这题有详细解释。

迭代法

迭代的精髓在于按顺序对指针指向的扭转。以1->2->3->4为例，当迭代到第三次时，前面的运算已经保存了一个pre值，值为2->1，这时到3这个节点，只需把它的指向指到pre即可，而构成的新的链表3->2->1保存为pre以供下次迭代，但是因为它后面的值还要做运算，所以把它原先的指向先保存起来（为next），为了下次继续迭代。

class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        var pre: ListNode? = nil
        var cur = head
        while cur != nil {
            let t = cur?.next
            cur?.next = pre
            pre = cur
            cur = t
        }
        return pre
    }
}

递归法

递归的精髓在于将next当做参数传入reverseList函数时，在下一次递归中对参数的操作，会反应在上次的参数值上。
还是以1->2->3->4举例子，4次递归后（回溯前），其实是将引用链全部打破：

class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        //递归终止条件是当前为空，或者下一个节点为空
        if head == nil || head?.next == nil {
            return head
        }
        //这里的cur就是最后一个节点
        let cur = reverseList(head?.next)
        //如果链表是 1->2->3->4->5，那么此时的cur就是5
		//而head是4，head的下一个是5，下下一个是空
		//所以head.next.next -> head 就是5->4
        head?.next?.next = head
        //防止链表循环，需要将head.next设置为空
        head?.next = nil
        //每层递归函数都返回cur，也就是最后一个节点
        return cur
    }
}

**版权声明**

Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文首发于Ivan’s Blog | 叶帆的博客博客（ http://yeziahehe.com ），版权所有，侵权必究。

本文链接：http://yeziahehe.com/2017/11/06/ReverseLinkedList/