反转链表

http://www.nowcoder.com/questionTerminal/75e878df47f24fdc9dc3e400ec6058ca

第一种：递归法

解释一下：

经过head.next.next=head;使得head.next的next指针指向head

经过head.next=null;使得head的next指针指向空

所以这两句语句的作用就是使head与head->next的指向反转。

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        //递归实现
        if(head==null||head.next==null){//链表为空或者只有一个元素
            return head;
        }
        //先反转后面的链表，走到链表的末端结点
        ListNode p = ReverseList(head.next);
         //再将当前节点设置为后面节点的后续节点
        head.next.next=head;
        head.next=null;
        return p;
    }
}

第二种：头插法

解释：这里涉及到head，pre，next三个结点

作用：使原本指向为head->(head->next)变为(head->next)->head

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null||head.next==null){//该链表无结点或只有一个结点
            return head;
        }
        ListNode pre = null;
        ListNode next = null;
        while(head!=null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

第三种：遍历+栈保存

最后，附上测试代码，只需改动ReverseList函数的内容，其他无需改动

class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
        this.val = val;
    }
}
class Solution {
	public static ListNode ReverseList(ListNode head) {
        //递归实现
        if(head==null||head.next==null){//链表为空或者只有一个元素
            return head;
        }
        //先反转后面的链表，走到链表的末端结点
        ListNode p = ReverseList(head.next);
         //再将当前节点设置为后面节点的后续节点
        head.next.next=head;
        head.next=null;
        return p;
    }
	public static void Myprint(ListNode t1)
	{
		while(t1!=null){
    		System.out.println(t1.val);
    		t1=t1.next;
    	}
	}
	public static void main(String[] args) {
		ListNode t1 = new ListNode(1);
    	ListNode t2 = new ListNode(2);
    	ListNode t3 = new ListNode(3);
    	
    	t1.next=t2;
    	t2.next=t3;
    	t3.next=null;
    	
    	Myprint(t1);
    	System.out.println("--------反转之后的链表-------");
    	ListNode r = ReverseList(t1);
    	Myprint(r);
	}
}