题解 | #反转链表#

好像几乎所有人都是递归解法，没有迭代解法，我就来说说迭代解法的思路：
如果一个节点是头结点 head ，后面连着一串节点，如何让该节点的指向反转呢？

head.next.next = head;
head.next = null;

这是针对于每个节点的反转操作，请画图理解一下。
如果对于每个节点都按照这样的解法操作，我们就能对每个节点进行节点的反转，迭代截止条件是 head == null 或者 head.next == null，为什么是这个条件呢？因为我们需要找到这个链表的最后一个节点，最后一个节点的下一个节点若为空，则说明已经找到了最后一个节点，直接返回作为头结点即可。当头结点都为空的时候，我们直接返回头结点即可，链表无需反转。

public class Solution {
    public ListNode ReverseList(ListNode head) {
        //递归版本
        if(head==null || head.next==null)
            return head;
        ListNode res = ReverseList(head.next);
        head.next.next = head;
        head.next = null;
        return res;
    }
}

再来一个递归版本的解法，比较容易理解

public class Solution {
    public ListNode ReverseList(ListNode head) {

        //迭代版本
        ListNode pre=null;
        ListNode cur=head;
        while(cur!=null){
            ListNode tmp=cur.next;
            cur.next = pre;
            pre = cur ;
            cur = tmp;
        }
        return pre;

    }
}