java - 为链接列表创建 getLast 方法

Question

我正在尝试用 Java 手动编写 getLast 方法。我知道我必须做什么，只是在编码方面遇到了麻烦。我需要做的是遍历链表，直到 p.link 指向 null，然后我可以添加到列表的末尾。这是我到目前为止所拥有的:

class MyLinkedList 
{
   private class Node           
   {
      private Node link;
      private int x;
   }
   //----------------------------------
   private Node first = null;    
   //----------------------------------
   public void addFirst(int d)
   {
      Node newNode = new Node(); 
      newNode.x = d;            
      newNode.link = first;      
      first = newNode;           
   } 

   public void addLast(int q)
   {
      Node newNode = new Node();
      newNode.x = q;
      newNode.link = null;  //points to null because nothing should follow it
   //----------------------------------
   public void traverse()
   {
      Node p = first;
      while (p != null)            
      {
         System.out.println(p.x);  
         p = p.link;               
      }
   }
}
//==============================================
class C15h1  
{
   public static void main(String[] args)
   {
      MyLinkedList list = new MyLinkedList();
      list.addLast(4);
      list.addLast(5);
     list.addLast(6);
      list.addFirst(1);
      list.addFirst(2);
      list.addFirst(3);
      System.out.println("Numbers on list");
      list.traverse();
   }
}

Answer 1

我会跟踪最后一个节点:

class MyLinkedList 
{
   private class Node           
   {
        private Node link;
        private int x;
   }
    //----------------------------------
    private Node first = null;    
    private Node last = null;    
    //----------------------------------

    public void addFirst(int d)
    {
        Node newNode = new Node(); 
        newNode.x = d;            
        newNode.link = first;      
        first = newNode;
        if(last == null)
            last = newNode;           
    } 

    public void addLast(int q)
    {
        Node newNode = new Node();
        newNode.x = q;
        newNode.link = null;  //points to null because nothing should follow it
        if(last != null)
            last.link = newNode;
        last = newNode;
        if(first == null) // This is the first node
            first = newNode;
    }

    //----------------------------------
    public void traverse()
    {
        Node p = first;
        while (p != null)            
        {
            System.out.println(p.x);  
            p = p.link;               
        }
    }

    public int getLast()
    {
        if(last != null)
            return last.q;
        return -1;
    }
}