_206.java

package com.fishercoder.solutions;

import com.fishercoder.common.classes.ListNode;

/**
 * 206. Reverse Linked List
 *
 * Reverse a singly linked list.*/
public class _206 {

    /**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) {
        /**It works out the best to set up a debug point and visualize this process:
         * e.g. 1->2->3-null
         * at the end of the first iteration of the while loop, the status is like this:
         * newHead: 1->null
         * head: 2->3-null
         * then it continues the iteration.*/
        ListNode newHead = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = newHead;
            newHead = head;
            head = next;
        }
        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);
    }

    ListNode reverse(ListNode head, ListNode newHead) {
        if (head == null) {
            return newHead;
        }
        ListNode next = head.next;
        head.next = newHead;
        newHead = head;
        head = next;
        return reverse(head, newHead);
    }

}