Reverse a singly linked list.
Thoughts:
1.Iterative Method.
Loop the linked list, set two pointers, one called "first" to always point to the head of the list, the other called "tail" to mark the currently looped element, each time we loop to that element, we switch the first and tail element to iteratively finish the reverse function.
Code:
public ListNode reverseList(ListNode head) { ListNode first = null; ListNode tail = head; ListNode tmp; while(tail!=null){ tmp=first; first = tail; tail=tail.next; first.next=tmp; } return first; }
2.Recursive Method
There‘s code in one reply that spells it out, but you might find it easier to start from the bottom up, by asking and answering tiny questions (this is the approach in The Little Lisper):
Code:
public ListNode Reverse(ListNode list) { if (list == null) return null; // first question if (list.next == null) return list; // second question // third question - in Lisp this is easy, but we don‘t have cons // so we grab the second element (which will be the last after we reverse it) ListNode secondElem = list.next; // bug fix - need to unlink list from the rest or you will get a cycle list.next = null; // then we reverse everything from the second element on ListNode reverseRest = Reverse(secondElem); // then we join the two lists secondElem.Next = list; return reverseRest; }
原文：http://www.cnblogs.com/midan/p/4656006.html