CODEWITHSUNDEEP
javaalgorithmcomplexity-theory
volk
volk

Reputation: 1196

Complexity of this reverse singly linked list algorithm?

What is the complexity of this algorithm? I am assuming it's O(N) but I'd like some clarification. If I had a tail in the linked list, I would assume this would be even faster since I would completely avoid having that while(current != null) loop to loop to the end of the list.

public void reverse() {
    Stack<Node> stack = new Stack<Node>();
    if (this.head != null || this.head.next != null) {
        Node current = this.head;
        while (current != null) {
            stack.push(current);
            current = current.next;
        }
        Node last = null;
        while (!stack.empty()) {
            if (last==null) {
                this.head = stack.pop();
                last = this.head;
                continue;
            }
            last.next = stack.pop();
            last = last.next;
            if (stack.empty()) {
                last.next = null;
            }
        }
    }
}

Upvotes: 1

Views: 3080

Answers (2)

SDwarfs
SDwarfs

Reputation: 3239

The algorithm is in class O(N). You are using N times a static amount of operations (first loop) and then again a static amount of operations (second loop); Stack.pop() should be independent of "N"; So this means it's in class O(2N+c)... and O(2N+c) is in class O(2N) which is in O(N). In other words: the runtime of your routine increases linear with your number of elements in the stack.

OR simply: Yes, it is in class O(N).

Upvotes: 1

ams
ams

Reputation: 62792

You are pushing all the linked list elements onto stack by iterating the list this is one N then you iterate the stack which is another N so you Order notation in O(2N)

see how to reverse a list with O(1) space and O(n) time?

Upvotes: 3

Related Questions