package com.freetymekiyan.algorithms.level.easy;

/**
 * Reverse a singly linked list.
 * <p>
 * click to show more hints.
 * <p>
 * Hint:
 * A linked list can be reversed either iteratively or recursively. Could you implement both?
 * <p>
 * Company Tags: Uber, Facebook, Twitter, Zenefits, Amazon, Microsoft, Snapchat, Apple, Yahoo, Bloomberg, Yelp, Adobe
 * Tags: Linked List
 * Similar Problems: (M) Reverse Linked List II, (M) Binary Tree Upside Down, (E) Palindrome Linked List
 */
public class ReverseLinkedList {

    /**
     * Recursive.
     * <p>
     * Divide the list into 2 parts - head and the rest starts from head.next.
     * Reverse the rest of the linked list.
     * Append head to the tail of reversed linked list, which is head's next.
     * Return newHead of the reversed linked list.
     */
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) { // 1 or no node
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    /**
     * Iterative.
     * Create a new head.
     * Loop through the list.
     * For each node, get its next first.
     * Point itself to the previous head.
     * Move previous head to current node.
     * Then move to the next node and do the same thing.
     * Stop when reach the end.
     */
    public ListNode reverseList2(ListNode head) {
        ListNode newHead = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = newHead;
            newHead = head;
            head = next;
        }
        return newHead;
    }

    public class ListNode {

        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}

@@ -545,19 +545,8 @@
 ve.%0A
-     * %3Cp%3E%0A
     
@@ -906,20 +906,34 @@
  // 
-1 or no
+Empty list or just 1
  node
+.
 %0A   
@@ -1014,16 +1014,42 @@
 d.next);
+ // Similar to post-order.
 %0A       
@@ -1166,148 +1166,229 @@
   * 
-Create a new head.%0A     * Loop through the list.%0A     * For each node, get its next first.%0A     * Point itself to the previous
+Get one node each time and make it the new head of the reversed list.%0A     * Create a head of the linked list as null.%0A     * Use the original head as a pointer to iterate the list.%0A     * While the original
  head
-.
+:
 %0A     * 
 Move
@@ -1387,50 +1387,43 @@
   * 
-Move previous head to current node
+%7C First store the next head
 .%0A     *
  The
@@ -1422,89 +1422,110 @@
    *
+ %7C
  Then 
-move to the next node and d
+set head.next to newHead.%0A     * %7C Move newHead t
 o 
-t
 he
- same thing.%0A     * Stop when reach the end
+ad.%0A     * %7C Move head to its stored next
 .%0A  

update reverse linked list