Reverse Linked List

Reverse a singly linked list.

Hint: A linked list can be reversed either iteratively or recursively. Could you implement both?

Naive Thinking: At first, I thought it cannot be done in O(1) space, so I use a stack and go through the linked-list once pushing one by one into stack. And then pop from the stack one by one. Not surprisingly, I got memory limit exceed. That's probably a sign that I used extra space. So I begin to think about using O(1) space. Just pointing each Node's next pointer to its previous one. In such a process, I need to always note down its next Node first or I will lost the remaining Nodes.

Iteratively:

 /**  
  * Definition for singly-linked list.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   // iteratively  
   public ListNode reverseList(ListNode head) {  
     ListNode pre = null, cur = head, next = null;  
     while(cur!=null){  
       next = cur.next;  
       cur.next = pre;  
       pre = cur;  
       cur = next;  
     }  
     return pre;  
   }  
 }  

Recursively:

 public class Solution {  
   // recursively  
   public ListNode reverseList(ListNode head) {  
     return reverseList(null, head);  
   }  
   private ListNode reverseList(ListNode pre, ListNode cur){  
     // ending case  
     if(cur==null) return pre;  
     // general case  
     ListNode next = cur.next;  
     cur.next = pre;  
     return reverseList(cur, next);  
   }  
 }