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 curr开发者_如何学Goent=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;
}
}
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?).
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;
}
}
精彩评论