反转链表问题java实现

 双指针方法：

package 链表;

import java.awt.List;

import javax.xml.soap.Node;

public class 反转链表 {
public ListNode reverseList(ListNode head) {
	ListNode prev=null;
	ListNode cur=head;
	while(cur!=null) {
		ListNode temp=cur.next;
		cur.next=prev;
		prev=cur;
		cur=temp;
	}
	return prev;
}
}
class ListNode{
	 int value;
	 ListNode next;

	public ListNode(int value, ListNode next) {
		super();
		this.value = value;
		this.next = next;
	}
	
	 
}

递归方法：

package 链表;

import java.awt.List;

import javax.xml.soap.Node;

public class 反转链表 {
//	2.递归回溯
public ListNode reverseList2(ListNode head) {
	//1.首先递归结束条件
	if(head==null||head.next==null) {
		return head;//1.2最小子问题
	}
	 ListNode p=reverseList(head.next);//开始回溯,p就是反转后的第一个节点
	//子问题与父问题的求解方式
	head.next.next=head;
	head.next=null;
	return p;
}
	//	1.双指针法
public ListNode reverseList(ListNode head) {
	ListNode prev=null;
	ListNode cur=head;
	while(cur!=null) {
		ListNode temp=cur.next;
		cur.next=prev;
		prev=cur;
		cur=temp;
	}
	return prev;
}
}
class ListNode{
	 int value;
	 ListNode next;

	public ListNode(int value, ListNode next) {
		super();
		this.value = value;
		this.next = next;
	}
	
	 
}