在常数时间内将元素添加到单向链表的末尾

Question

我正在尝试编写一种在常数时间内向单链表末尾添加元素的方法。我不知道如何在常数时间内将指针分配给列表中的最后一个节点。该方法运行时间为0(n)：

public void insertEnd(Object obj) {
if (head == null) {
  head = new SListNode(obj);
} else {
  SListNode node = head;
  while (node.next != null) {
    node = node.next;
  }
  node.next = new SListNode(obj);
}
size++;
}

这是我的新方法的开端：

public void addLast(SListNode obj){
  //if the list is empty, the new element is head and tail
  if(tail == null){  
      obj.next = null;
      head = tail = obj;
  }else{   -----> here I'm confused 

  }
}

这是我的SList类：

public class SList {
   private SListNode head;
   private SListNode tail;
   private int size;

   public SList() {
   size = 0;
   head = null;
   tail = null;

}

- Dodi

---

在类中加入一个字段来存储列表的末尾，你觉得可行吗？ - zw324

我做到了，但是你如何将其分配给最后一个元素？ - Dodi

@Frugo，tail.next = obj; - BLuFeNiX

我能在这个帖子上得到一些更新吗？ - Naveen Niraula

Answer 1

我认为这应该就可以了：（应该放在else中）

tail.next = obj; // have (the current tail).next point to the new node
tail = obj; // assign 'tail' to point to the new node
obj.next = null; // may not be required

- Bernhard Barker

Answer 2

你需要实现一个双端队列，允许在列表的头部或尾部插入。如果列表为空，则头和尾都为null；如果它包含一个元素，则head == tail。

public void addLast(SListNode obj){
//if the list is empty, the new element is head and tail
if(tail == null){  
  obj.next = null;
  head = tail = obj;
}else{   -----> here I'm confused 
  tail.next = obj;
  tail = obj;
}

- gma