Reverse LinkedList

只要用两个pointer， 一个(head)指向reverse之后linkedlist的头，一个（pt)指向原来linkedlist的下一个元素即可。

LinkedNode temp = head;

head = pt;

pt = pt.next;

head.next = temp;

Recursively:

1.

2.

We Assume that the rest of the list had already been reversed. For exmaple, the list is: n1→ … → nk-1→ nk→ nk+1→ … → nm→ Ø

Assume from node nk+1to nmhad been reversed and you are at node nk.

n1→ … → nk-1→nk→ nk+1← … ← nm

We want nk+1’s next node to point to nk.

So,

nk.next.next = nk;

Be very careful that n1's next must point to Ø. If you forget about this, your linked list has a cycle in it.

• Time complexity :O(n)O(n). Assume that n is the list's length, the time complexity isO(n)O(n).

• Space complexity :O(n)O(n). The extra space comes from implicit stack space due to recursion. The recursion could go up to n levels deep.