为链表创建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;
    }
}

Answer 2

这可能是您想要的？

public Node getLast()
{
    Node lastNode = first;
    Node next = first.link;
    while (next != null)
    { 
         lastNode = next;
         next = next.link; 
    }
    return lastNode;
}

Answer 3

当前代码中的问题出现在traverse()方法中。它循环到p == null，这意味着当p"掉"出列表时停止。您想要的是在这样的p指向列表的最后一项之前停止一步。要做到这一点，只需将条件从while (p != null)更改为while (p.link != null)。

以下是addLast()的外观：

public void addLast(int q)
{
   Node newNode = new Node();
   newNode.x = q;
   newNode.link = null;  //points to null because nothing should follow it
   Node p = first;
   while (p.link != null) {
      p = p.link;               
   }
   p.link = newNode;
}

Answer 4

使用while循环迭代直到得到最后一个节点，一旦找到最后一个，就返回它。.

 public Node getLast(){
    Node p = first;
          while (p.link != null)            
          { 
             p = p.link;               
          }
    return p;
    }

Answer 5

您需要循环浏览您的列表直到结束。（就像你提到的。"直到p.link指向null，"）

你可以这样做：

public void addLast(int q) {
    Node newNode = new Node();
    newNode.x = q;
    newNode.link = null;
    if (first == null) {
        first = newNode;
    } else {
        Node lastNode = first;
        while (lastNode != null && lastNode.link != null) {
            lastNode = lastNode.link;
        }
        lastNode.link = newNode;
    }
}