LeetCode 206. Reverse Linked List

原题链接在这里：https://leetcode.com/problems/reverse-linked-list/

题目：

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 }

AC JavaScript:

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

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: Recursion
12         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 }

跟上Reverse Linked List II, Reverse Nodes in k-Group, Binary Tree Upside Down.