CODEWITHSUNDEEP
javalinked-listreverse
user665319
user665319

Reputation: 1449

reverse linked list problem

I have the following linked list program in java which works fine excep for the reverse linked list function. What am i missing?

public class LinkedList {

private Link first;

public LinkedList()
{
    first = null;
}
public boolean isEmtpy()
{
    return(first==null);
}

public void insertFirst(int id, double dd)
{
    Link newLink=new Link(id,dd);
    newLink.next=first;     //new link --> old first
    first =newLink;         //first --> newLink
}
public Link deleteFirst()
{
    Link temp=first;
    first=first.next;
    return temp;
}
public void displayList()
{
    Link current=first;
    System.out.println("List (first-->last)");
    while(current!=null)
    {
        current.displayLink();
        current=current.next;
    }       
    System.out.println(" ");
}
public Link find(int key)
{
    Link current=first;

    while(current.iData!=key)
    {
        if(current.next==null)
            return null;    //last link
        else
            current=current.next;

    }
    return current;
}
public Link delete(int key)
{
    Link current=first;
    Link previous=first;

    while (current.iData!=key)
    {
        if (current.next==null)
            return null;
        else
        {
            previous=current;
            current=current.next;
        }
    }
    if(current==first)
        first=first.next;
    else
        previous.next=current.next;
    return current;     
}   

public void insertAfter(int key, int id, double dd)
{
    Link current=first;
    Link previous=first;

    Link newLink = new Link(id,dd);
    while (current.iData!=key)
    {
        if (current.next==null)
            System.out.println("At the last Node");
        else
        {
            previous=current;
            current=current.next;

        }
    }
    System.out.println("Value of previous "+ previous.iData);
    System.out.println("Value of current after which value will be inserted is " + current.iData);
    newLink.next=current.next;
    current.next=newLink;
}

public Link reverse()
{
    Link previous=null;
    Link current=first;
    Link forward;

    while(current!=null)
    {
        forward=current.next;
        current.next=previous;
        previous=current;
        current=forward;
    }
    return previous;
}
}

Upvotes: 2

Views: 1832

Answers (3)

Vinay Gade
Vinay Gade

Reputation: 7

// approach 1 : Iterative
public void reverseIterative() {

    if (isEmpty() || first.next == null)
        return;

    Link q = null;
    Link p = first;
    Link r;

    while(p != null) {
        r = p.next;
        p.next = q;
        q = p;
        p = r;
    }

    first = q;
}


// approach 2 : Recursive 
// returns first Link
public Link reverseRecursive(Link first){ //returns first

    if(isEmpty() || first.next == null)
        return first;

    Link newHead = reverseRecursive(first.next);
    first.next.next = first;
    first.next = null;
    return newHead;
}

Upvotes: 0

Sach
Sach

Reputation: 659

Here is changed code. You need to make last's next to null and reinitialize first.

public Link reverse()
{
    Link previous=null;
    Link current=first;
    Link forward;

    while(current!=null)
    {
        forward=current.next;
        current.next=previous;
        previous=current;
        current=forward;
    }
    first.next = null;
    first = previous;
    return previous;
}
}

Upvotes: 1

Péter Török
Péter Török

Reputation: 116266

The problem is, reverse() does not set first to its new value, so the linked list will become corrupted (effectively it will be reduced to the former head element).

You should add

first = previous;

in the end, before returning the value (or instead - do you really need to return the new head node?).

Upvotes: 7

Related Questions