Reverse Linked List

Problem

Reverse a singly linked list.

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

My original solution using the same idea from 92 Reverse Linked List in Leetcode

public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy, next = head.next;
        while (next != null) {
            head.next = next.next;
            next.next = prev.next;
            prev.next = next;
            next = head.next; //Cannot be next.next cause it is already modified, stick to the "Cycle Rule"
        }
        return dummy.next;
    }
}

Standard Iterative Solution: O(n) time and O(1) space

public class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode tempNext = head.next;
            head.next = prev;
            prev = head;
            head = tempNext;
        }
        return prev;
    }
}

Recursive Solution of above: O(n) time and O(n) space

public class Solution {
    public ListNode reverseList(ListNode head) {
        return helper(head, null);
    }

    private ListNode helper(ListNode head, ListNode prev) {
        if (head == null) return prev;
        ListNode tempNext = head.next;
        head.next = prev;
        return helper(tempNext, head);
    }
}

Standard Recursive Solution without Helper Function: O(n) time and O(n) space

public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

Analysis

There are three approaches to this problem
The first one is my original thought after solving the Reverse Linked List II problem
The second one is using iteration to change all pointers of next to prev
The third one is recursive version of the iterative solution
The last standard recursive is very interesting and kind of tying to solve the problem in a different direction
We first go to the tail of the given linked list, which will be the new head
Then in the middle, we change the point of next.next into itself, which indeed reversed the linked list
However, we need to set head.next = null to avoid the cycle in the linked list
Head.next will be set to correct node in the next call of recursion method
Notice that the first statement head == null is to check the case when linked list is null
The second statement is to find the tail of linked list