反向链表问题

Question

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

Answer 1

问题是，reverse() 不会将 first 设置为其新值，因此链表将被损坏（实际上它将被减少到以前的头元素）。

您应该

first = previous;

在返回值之前在最后添加（或者相反 - 您真的需要返回新的头节点吗？）。

Answer 2

这是更改后的代码。您需要将最后一个设置为空并首先重新初始化。

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

Answer 3

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