LeetCode Reverse Linked List: Recursive VS Iterative Solution

Overview

LeetCode Reverse Linked List: Recursive solution takes O(N) time and O(N) space while Iterative Solution takes O(N) time and O(1) space.

LeetCode Reverse Linked List

Reverse a singly linked list. Can you solve it both recursively and iteratively?

LeetCode Reverse Linked List Recursive and Iterative Solution

LeetCode Reverse Linked List: Recursive solution takes O(N) time and O(N) space while Iterative Solution takes O(N) time and O(1) space. And the following Java code could be accepted by LeetCode OJ to solve this Reverse Linked List problem.

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

	        int x = (Math.random() < 0.5) ? 0 : 1;

		if (x == 0) {
			return reverseListIteratively(head);
                } else {
			return reverseListRecursively(head);
                }
	}

	private ListNode reverseListIteratively(ListNode head) {

		if (head == null || head.next == null) {
			return head;
		}

		ListNode p1 = head, p2 = head.next, p3;
		p1.next = null;

		while (p2 != null) {
			p3 = p2.next;
			p2.next = p1;
			p1 = p2;

			p2 = p3;
		}

		return p1;
	}

	private ListNode reverseListRecursively(ListNode head) {

		if (head == null || head.next == null) {
			return head;
		}

		ListNode p1 = head.next;
		ListNode p2 = reverseListRecursively(p1);
		head.next = null;
		p1.next = head;

		return p2;
	}
}

**Note: **

  1. be careful about the recursive solution in case of StackOverFlow Exception, and another observation is that the first node and the last node of the reversed linked list is known directly, right?
  2. Also take a look at this generalized problem to reverse a linked list from position m to n: LeetCode Reverse Linked List II: One Pass 

 

Summary

LeetCode Reverse Linked List: Recursive solution takes O(N) time and O(N) space while Iterative Solution takes O(N) time and O(1) space.

Written on July 12, 2015