CODEWITHSUNDEEP
linked-listreverse
ueg1990
ueg1990

Reputation: 1033

Reverse a linked list using constant amount of addtional space

Following is my code to reverse a linked list:

public LinkedList reverse() {
    LinkedList m = new LinkedList();
    Node temp = this.getHeadNode();
    while(temp!= null) {
        m.insertFirst(temp.getElement());
        temp = temp.getNext();
    }
    m.getTailNode().setNext(null);
    return m;
}

For the local variable LinkedList m i declared in my function, does that mean i am using O(n) amount of additional space or is it considered constant amount of space?

Upvotes: 0

Views: 1424

Answers (5)

Murtaza Zaidi
Murtaza Zaidi

Reputation: 597

This is my approach for reversing LinkedList in linear time and constant space implemented in C#. I hope it helps. We are just reversing the links between nodes and making first node last and last node first.

        Node p1, p2, t1, t2;
        p1 = head;
        p2 = p1.next;
        while (p2 != null)
        {
            t1 = p2;
            t2 = p2.next;
            p2.next = p1;
            p1 = t1;
            p2 = t2;
        }
        head.next = null;
        head = p1;

Upvotes: 0

birubisht
birubisht

Reputation: 908

just take three pointer initialize all three at start suppose these pointer are x,y,z then move y=x->next,z=y->next ,y->next=x,x=y; do this until x reaches end of the list .

Upvotes: 1

ueg1990
ueg1990

Reputation: 1033

this is what i did:

public LinkedList reverse1() {
    Node temp1 = tail;
    Node temp2 = head;
    Node temp3 = new Node(this.removeFirst());
    temp1.setNext(temp3);
    temp3.setNext(null);
    //head = temp1;
    tail = temp3;
    while(head != temp1) {
        temp2 = new Node(this.removeFirst());
        temp2.setNext(temp3);
        temp1.setNext(temp2);
        temp3 = temp2;
    }
    return this;
}

is this good enough?

Upvotes: 0

birubisht
birubisht

Reputation: 908

hi I think one better approach could be reversing the link list without creating the secondary list .

Upvotes: 1

jdevelop
jdevelop

Reputation: 12296

since you're creating new instance of linked list - you will have 2 copies of list in memory. The list will contain references to objects, so if you want to count instances of objects - then you are safe and amount of additional memory is O(1). But list itself takes some memory, so if you count number of "cells" in lists - then yes, you have O(N) additional memory being used.

Upvotes: 0

Related Questions