Reverse Linked List Solutions in Java

// Source : https://leetcode.com/problems/reverse-linked-list/description/
// Author : Tianming Cao
// Date   : 2018-02-11


package reverseLinkedList;

public class ReverseLinkedList {

	/**
	 * The iterative solution
	 */
	public ListNode reverseList(ListNode head) {
		if (head == null) {
			return head;
		}
		ListNode p = head;
		ListNode next = p.next;
		while (next != null) {
			ListNode temp = next.next;
			next.next = p;
			p = next;
			next = temp;
		}
		head.next = null;
		return p;
	}
	
	public ListNode reverseListRecursion(ListNode head) {
		if (head == null) {
			return head;
		}
		ListNode newHead = recursion(head);
		head.next = null;
		return newHead;
	}
	/**
	 * The recursive solution
	 */
	public ListNode recursion(ListNode p) {
		if (p.next == null) {
			return p;
		} else {
			ListNode next = p.next;
			ListNode newHead = recursion(next);
			next.next = p;
			return newHead;
		}
	}

}

/// Source : https://leetcode.com/problems/reverse-linked-list/description/
/// Author : liuyubobobo
/// Time   : 2017-11-15

/// Iterative
/// Time Complexity: O(n)
/// Space Complexity: O(1)
public class Solution1 {

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

    public ListNode reverseList(ListNode head) {

        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }
}

/// Source : https://leetcode.com/problems/reverse-linked-list/description/
/// Author : liuyubobobo
/// Time   : 2017-11-15

/// Recursive
/// Time Complexity: O(n)
/// Space Complexity: O(n)
public class Solution2 {

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

    public ListNode reverseList(ListNode head) {

        // 递归终止条件
        if(head == null|| head.next == null)
            return head;

        ListNode rhead = reverseList(head.next);

        // head->next此刻指向head后面的链表的尾节点
        // head->next->next = head把head节点放在了尾部
        head.next.next = head;
        head.next = null;

        return rhead;
    }
}