Reverse Linked List

#记录经典问题，方便以后复习。

题目：

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

1、非递归

public static ListNode reverseList1(ListNode head) {
		ListNode prev = null; //当前节点的前一个节点
	    ListNode curr = head; //当前节点
	    while (curr != null) {
	        ListNode nextTemp = curr.next;  //当前节点的下一个节点
	        curr.next = prev;
	        prev = curr;
	        curr = nextTemp;
	    }
	    return prev; //当前节点指向了null,所以返回当前节点的上一个节点
    }

2、递归

public static ListNode reverseList2(ListNode head) {
		if (head == null || head.next == null) return head;
	    ListNode p = reverseList(head.next); 
	    head.next.next = head;
	    head.next = null;
	    return p;   
    }