проблема обратного связанного списка - PullRequest
Новая
       41

проблема обратного связанного списка

2 голосов
/ 01 апреля 2011

У меня есть следующая программа связанного списка в Java, которая прекрасно работает, кроме функции обратного связанного списка. Чего мне не хватает? 

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;
}
}

Ответы [ 3 ]

7 голосов
/ 01 апреля 2011

Проблема в том, что reverse() не устанавливает first в новое значение, поэтому связанный список будет поврежден (фактически он будет уменьшен до прежнего элемента head).

Вы должны добавить 

first = previous;

в конце, перед возвратом значения (или вместо этого - вам действительно нужно вернуть новый головной узел?).

0 голосов
/ 05 июня 2012

Здесь изменен код.Вам нужно сделать последний после нуля и сначала переинициализировать. 

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;
}
}
0 голосов
/ 01 апреля 2011

Новая голова возвращается, правильно? Я думаю, что следующий начальный заголовок должен быть установлен в ноль, или он будет проходить между двумя последними элементами при обходе списка.

Хе, неважно ...

...