题目：
Reverse a singly linked list.
链接： http://leetcode.com/problems/reverse-linked-list/
2/25/2017, Java
之前的错误：看起来第一遍没有任何问题，但是1->2居然是time limit exceeded。为什么呢？原因是缺了第9行，没有把最后开始的第一个元素的next设为null。这样的话最后两个元素是一个圈。
1 public class Solution { 2 public ListNode reverseList(ListNode head) { 3 if (head == null) return head; 4 ListNode cur = new ListNode(0); 5 ListNode next = new ListNode(0); 6 ListNode prev = new ListNode(0); 7 prev = head; 8 cur = head.next; 9 prev.next = null; 10 while (cur != null) { 11 next = cur.next; 12 cur.next = prev; 13 prev = cur; 14 cur = next; 15 } 16 return prev; 17 } 18 }
别人的算法：用了一个dummy node
dummy的用法是dummy.next其实是prev，这样就跟之前对起来了，而且因为dummy一开始是没有加到list当中去的，最开始dummy.next是null。所以可以免去了前例里面的第9行。注意第7行也是可以的，对Java要熟练哦。
1 public class Solution { 2 public ListNode reverseList(ListNode head) { 3 if (head == null || head.next == null) return head; 4 ListNode dummy = new ListNode(0); 5 6 while (head != null) { 7 ListNode tmp = head.next; 8 head.next = dummy.next; 9 dummy.next = head; 10 head = tmp; 11 } 12 return dummy.next; 13 } 14 }
之前还用了stack的方法，也是time limit exceeded，没有细究，估计原因是把每个list node放入栈内，但是node中next的值并没有更新。所以无论做了什么，也是然并卵。
原文：http://www.cnblogs.com/panini/p/6443551.html