algorithm - 实现一种算法，在不遍历的情况下将节点插入循环链表

Question

我在想解决这个问题的方法。

我的输入:
1. 有一个指向最后一个节点的尾指针。
2. 知道最后一个指针后，您可以轻松地在它旁边添加一个新节点。

Void Insert(Node N)
{  
    if (head == null) // linked list is empty
    {
       head = N; tail = N; tail.Next = head;
    } 
    else
    {        
      Node temp = tail.Next; // since this is circular tail will point to head
      Tail.Next = N;
      N.Next = temp; // correct 
      tail = N;       
    }
}

有没有人能想出不使用尾指针的更好解决方案？也如问题中所述，无需遍历？这是一个面试问题，只需要一些输入即可找到最佳解决方案。

Answer 1

我猜你有一个单链循环列表，只有一个指向一个元素的指针(称之为头节点)。因此，列表的每个节点都包含一个值和一个指向下一个元素的指针。尾节点指向头节点。在头节点之后直接插入一个节点是微不足道的。我猜您想直接在头节点之前插入一个节点。为此，您需要新节点成为最后一个节点，它从前一个最后一个节点指向，并指向头节点。现在，您希望避免遍历列表来查找最后一个节点。这意味着您无法访问最后一个节点，因此无法修改其指针。使这项工作的唯一其他方法是修改最后一个节点指向的位置，即:

1. 在头节点之后插入一个新节点
2. 将当前头节点的值复制到那个新节点
3. 将新值放入当前头节点
4. 使新节点成为新的头节点