【剣指offer】逆転チェーン（再帰＋非再帰）

タイトル:
チェーンを入力して、チェーンを反転させた後、チェーンのすべての要素を出力します。
分析:
リンクの方向を変えるだけで、方向を変えるときは、元々のリンクの方向を前の接合点に向ける必要がありますので、次の3つの結点を記録する必要があります。
実現：（再帰ではない）

public ListNode ReverseList(ListNode head) {
	ListNode cur = head;
	ListNode next = null;
	ListNode pre = null;
	if (head == null || head.next == null) {
		return head;
	}
	while (cur != null) {
		next = cur.next;
		//      
		cur.next = pre;
		//     ，    
		pre = cur;
		cur = next;
	}
	return pre;
}

実現：再帰：

public ListNode Reverse(ListNode head) {
	if (head == null || head.next == null) {
		return head;
	}
	ListNode secondElem = head.next;
	head.next = null;
	ListNode reverseRest = Reverse(secondElem);
	secondElem.next = head;
	return reverseRest;
}