both iterative and recursive solutions for Reverse Linked List.

fishercoder1534 · fishercoder1534 · commit fd548a841cdd · 2016-08-17T10:01:29.000-07:00
diff --git a/EASY/src/easy/ReverseLinkedList.java b/EASY/src/easy/ReverseLinkedList.java
@@ -4,8 +4,12 @@
 import classes.ListNode;
 
 public class ReverseLinkedList {
-    //there's no reversion if the list is null or it contains only one node, so at a minimum, there should be 2 nodes
-    public ListNode reverseList(ListNode head) {
+    //creating a newHead = null is a very common/smart way to handle such cases, the logic flows out very naturally:
+	//create a new node called "next" to hold current head's next node
+	//then we could redirect head's next pointer to point to newHead which is head's previous node
+	//the above two steps finished the reversion, to continue this process until we reach the end of the original list, 
+	//we'll assign current "head" to new "newHead", and current "next" to be new "head" for the next iteration, here's the code
+    public ListNode reverseList_iterative(ListNode head) {
         ListNode newHead = null;
         while(head != null){
             ListNode next = head.next;
@@ -15,16 +19,44 @@ public ListNode reverseList(ListNode head) {
         }
         return newHead;
     }
+    
+    //following the above iterative version, the recursive solution flows out so naturally, basically, we just replaced the while loop with a recursive function
+    //still, a null newHead proves to be very helpful.
+    public ListNode reverseList_recursive(ListNode head) {
+    	ListNode newHead = null;
+    	return reverse(head, newHead);
+    }
+
+    private ListNode reverse(ListNode head, ListNode newHead) {
+    	if(head != null){
+    		ListNode next = head.next;
+    		head.next = newHead;
+    		newHead = head;
+    		head = next;
+    		return reverse(head, newHead);
+    	}
+    	else return newHead;
+	}
+    
+    //the above recursive function could of course be shortened to below, but the above one is just more intuitive and easier to follow and sort out your logic
+    private ListNode reverse_more_concise(ListNode head, ListNode newHead) {
+    	if(head != null){
+    		ListNode next = head.next;
+    		head.next = newHead;
+    		return reverse_more_concise(next, head);
+    	} else return newHead;
+    }
 
-    public static void main(String...strings){
+	public static void main(String...strings){
         ReverseLinkedList test = new ReverseLinkedList();
         ListNode head = new ListNode(1);
         head.next = new ListNode(2);
         head.next.next = new ListNode(3);
         head.next.next.next = new ListNode(4);
         head.next.next.next.next = new ListNode(5);
         CommonUtils.printList(head);
-        ListNode result = test.reverseList(head);
+//        ListNode result = test.reverseList_iterative(head);
+        ListNode result = test.reverseList_recursive(head);
         CommonUtils.printList(result);
     }
 
