Algs4-1.3.30反转链表

1.3.30编写一个函数，接受一条链表的首结点作为参数，（破坏性地）将链表反转并返回结果链表的首结点。迭代方式的解答：为了完成这个任务，我们需要记录链表中三个连续的结点：reverse、first和second。在每轮迭代中，我们从原链表中提取结点first并将它插入到逆链表的开头。我们需要一直保持first指向原链表中所有剩余结点的首结点，second指向原链表中所有剩余结点的第二个结点，reverse指向结果链表中的首结点。
答：  public void reverse()

public class LinkedList<Item>
{
    private class Node
    {
        Item item;
        Node next;
    }  
    //
    private int N;
    private Node first;
    public  Item deleteTail()
    {
        Item item;
        if (first==null)
            item=null;
        else if (first.next==null)
        {
            item=first.item;
            first=null;
            N--;
         }
        else
        {
           Node current=first;
           while(current.next.next!=null)
               current=current.next;
           item=current.next.item;
           current.next=null;
           N--;
        }
        return item;
    }//end deleteTail
   
    public boolean find(Item key)
    {
        boolean result=false;
        Node current=first;
        while(current!=null && !result)
        {
            result=current.item==key;
            current=current.next;
        }
        return result;
     }//end find
   
    public Item removeAfter(Node current)
    {
        Item item;
        if(current==null || current.next==null)
            item= null;
        else
        {
            item=current.next.item;
            current.next=current.next.next;
            N--;
        }
        return item;
     }//removeAfter
   
    public void insertAfter(Node one,Node two)
    {
       if(N==0)
           first=two;
       else
       {
         two.next=one.next;
         one.next=two;
       }
        N++;
    }//end insertAfter
   
    public void insertToFirst(Item item)
    {
        Node newFirst=new Node();
        newFirst.item=item;
        newFirst.next=first;
        first=newFirst;
        N++;
     }
   
    public void reverse()
    {
        if(N==0) return ;
        Node oldfirst=first;
        Node second=first.next;
        Node third=null;
        if (second!=null) third=second.next;
       
        while(second!=null)
        {
            second.next=first;
            first=second;
            second=third;
            third=null;
            if(second!=null) third=second.next;
        }
        oldfirst.next=null;
    }
   
    public void reverse2()
    {//书上的实现
        Node reverse=null;
        while(first!=null)
        {
            Node second=first.next;
            first.next=reverse;
            reverse=first;
            first=second;
        }
       first=reverse;
    }
   
public Node reverse3(Node first)
{//书上的递归实现，要调整 后才能正确运行
if (first == null) return null;
if (first.next == null) return first;
Node second = first.next;
Node rest = reverse3(second);
second.next = first;
first.next = null;
return rest;
}
    public void showAllNode()
    {
        Node current=first;
        while(current!=null)
        {
            Item item=current.item;
            StdOut.println(item);
            current=current.next;
        }

    }
   
    public int size()
    {
        return N;
    }
   
    public static void main(String[] args)
    {
       LinkedList<String> list=new LinkedList<String>();
       while(!StdIn.isEmpty())
       {
           String item=StdIn.readString();
           list.insertToFirst(item);
       }
       //
       StdOut.println("size="+list.size());
       list.showAllNode();
       list.reverse2();
       StdOut.println("---------");
       list.showAllNode();
    }
}