算法修炼15、反转链表

题目描述：

  输入一个链表，反转链表后，输出新链表的表头。

  解题思路：

  本题比较简单，有两种方法可以实现：（1）三指针。使用三个指针，分别指向当前遍历到的结点、它的前一个结点以及后一个结点。将指针反转后，三个结点依次前移即可。（2）递归方法。同样可以采用递归来实现反转。将头结点之后的链表反转后，再将头结点接到尾部即可。

  编程实现（Java）：

    //方法一：三指针
    public ListNode ReverseList(ListNode head) {
        if(head==null)
            return null;
        ListNode first=null; 
        ListNode second=head;
        ListNode third=head.next;
        while(third!=null){ 
            second.next=first; //三指针之间的变换
            first=second;
            second=third;
            third=third.next;
        }
        second.next=first;
        return second;
    }

    //方法二：递归
    public ListNode ReverseList(ListNode head) {
    	 if(head==null||head.next==null)
            return head;
        ListNode temp=ReverseList(head.next);
        head.next.next=head;
        head.next=null;
        return temp;   
    }