CODEWITHSUNDEEP
javabig-o
John
John

Reputation: 43

BIg-Oh for reversing LinkedList in Java

Please advise what would be the Big-O in these two cases. I understand that the base case would be constant O(1), but am confused how to compute for the rest and the recursion.

Case #1

public ListNode reverse1(ListNode list) {
    if (list == null || list.next == null) {
        return list;
    }
    ListNode after = reverse(list.next);
    list.next.next = list;
    list.next = null;
    return after;
}

Case #2

public ListNode reverse2(ListNode list) {
    if (list == null || list.next == null) {
        return list;
    }
    ListNode after = reverse2(list.next);
    ListNode temp = after;
    while (temp.next != null) {
        temp = temp.next;
    }
    temp.next = list;
    list.next = null;
    return after;
}

Upvotes: 3

Views: 424

Answers (2)

Joop Eggen
Joop Eggen

Reputation: 109603

Case #1a (Not an answer)

For those that want to see (one version of) a clean recursive list reversal. Especially without next.next.

public ListNode reverse1a(ListNode list) {
    return reverse1rec(list, null);
}

/**
 * Recursive reversal.
 * Following the technique of shifting (to-do part, done part).
 * @param list to be reversed (to-do).
 * @param reversed already reversed earlier (done).
 */
public ListNode reverse1rec(ListNode list, ListNode reversed) {
    if (list == null) {
        return reversed;
    }
    ListNode remaining = list.next;
    list.next = reversed;
    reversed = list; // For clarity.
    return reverse1rec(remaining, reversed);
}

Upvotes: 0

coder
coder

Reputation: 12982

In your first case the recursion gives:

T(n) = T(n-1) + c

where T(n) is the overall steps for n nodes, in order to reverse n nodes you just reverse n-1 in T(n-1) and add the nth node by doing constant operations which cost c (constant value doesn't matter).

The above recursive relation is easy to see that leads to:

T(n) = T(n-1) + c = T(n-2) + 2c =...= nc = O(n)

In your second case the recursion gives:

T(n) = T(n-1) + n + c

That's because in order to reverse n nodes you reverse n-1 in T(n-1) and you traverse the list in order to place the node at the end which cost n and constant operations which cost at most c (c doesn't matter).

The above recursive relation is easy to see that leads to:

T(n) = T(n-1) + n +c = T(n-2) + n + (n-1) + 2c =...= n(n-1)/2 +nc = O(n^2)

Upvotes: 2

Related Questions