ReverseLinkedList

ReverseLinkedList.java

public class ReverseLinkedList {
	public static void main(String[] args) {
	    ListNode head = new ListNode(2);
	    head.next = new ListNode(4);
	    head.next.next = new ListNode(6);
	    head.next.next.next = new ListNode(8);
	    head.next.next.next.next = new ListNode(10);

	    ListNode result = ReverseLinkedList.reverse2(head);
	    System.out.print("Nodes of the reversed LinkedList are: ");
	    while (result != null) {
	      System.out.print(result.val + " ");
	      result = result.next;
	    }
	  }
	
	
	static public ListNode reverse(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}
		
		ListNode prev = null;
		ListNode curr = head;
		ListNode next = null;
		while (curr != null) {
			next = curr.next; //保存下一个节点
			curr.next = prev; //当前节点指向已排序的节点
			prev = curr; //更新已排序节点
			curr = next; //更新当前节点
		}
		return prev;
	}
	
	static public ListNode reverse2(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}
		
		ListNode prev = reverse2(head.next);
		head.next.next = head;
		head.next = null;
		return prev;
	}
}