剑指offer----反转链表

题目：输入一个链表，反转链表后，输出链表的所有元素。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/

方法一 递归

public class Solution {
    ListNode node = null;
    public ListNode ReverseList(ListNode head) {
        if(head == null ||head.next == null){
            return head;
        }
        node = ReverseList(head.next);
    head.next.next = head;
        head.next = null;
        return node;
    }
}

一般情况下反转的问题利用递归代码写起来是比较简洁的，但是也用调用栈过深导致溢出的缺点，并且对递归函数调用前后的的代码块的特点也有要一定的理解。

• 函数调用之后的代码块一般都是按照递归栈，从栈底向栈顶反向执行的。
• 函数调用之前的代码快是从栈顶到栈底执行的。
• 所以判断递归的结束条件要在递归函数的调用之前进行，
• 而需要进行反向的代码在递归函数调用之后进行。

本题中，最终要返回反转之后的头结点，所以

• 可以确定return的值为最后一个节点，不断的向上浮动
• 然后就是节点之间的关系反转
  开始时第k个节点的next指向k+1，要将他反转过来变成k+1的next指向k。这个反转过程要从后向前进行。如果从前向后进行，就会导致1->2, 变成 2->1 和3节点就断开了。如果是反向的话4->5->6 反转之后是4->5<-6，链表仍然是相连接的。

方法二

public class Solution {
    ListNode node;
    public ListNode ReverseList(ListNode head) {
        ListNode first = null;
        ListNode second = null;
        while(head != null){
            first = head.next;
            head.next = second;
            second = head;
            head = first;
        }
        return second;
    }
}

上面使用递归的解释中提到，正向反转的话会出现链表断裂的情况，找不到下一个节点，那么我们可以使用一个指针一直指向下一个节点，然后将这个指针的next指向上一个节点即可。