原题链接在这里：

题目：

Reverse a singly linked list.

题解：

Iteration 方法：

生成tail = head, cur = tail, while loop 的条件是tail.next != null. 最后返回cur 就好。

Time Complexity: O(n).

Space O(1).

AC Java: 

1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { val = x; } 7  * } 8  */ 9 public class Solution {10     public ListNode reverseList(ListNode head) {11         if(head == null || head.next == null){12             return head;13         }14         ListNode tail = head;15         ListNode cur = head;16         ListNode pre;17         ListNode temp;18         while(tail.next != null){19             pre = cur;20             cur = tail.next;21             temp = cur.next;22             cur.next = pre;23             tail.next = temp;24         }25         return cur;26     }27 }

Recursion 方法:

reverseList(head.next)返回的是从head.next开始的reverse list，把head加在他的尾部即可。

他的尾部恰巧是之前的head.next, 这里用nxt表示。

Recursion 终止条件是head.next == null, 而不是head == null, head==null只是一种corner case而已。

Time Complexity: O(n), 先下去再回来一共走两遍.

Space O(n), 迭代用了stack一共O(n)大小, n 是原来list的长度。

AC Java:

1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { val = x; } 7  * } 8  */ 9 public class Solution {10     public ListNode reverseList(ListNode head) {11         //Method: Recursion12         if(head == null || head.next == null){13             return head;14         }15         16         ListNode nxt = head.next;17         ListNode newHead = reverseList(nxt);18         19         nxt.next = head;20         head.next = null;21         return newHead;22     }23 }

跟上, , .