实现一种算法,将节点插入循环链表而不遍历它

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. 使新节点成为新的头节点