数据结构-一次传递(扫描)和两次传递(扫描)之间的区别

Question

我前一天参加了一个面试。面试官让我写一个程序，在链表的末尾添加一个节点。我给了他一个解决办法。但他告诉我要在一次扫描中实现它。有人能告诉我，一次通过的意思是什么，以及如何发现程序写在一次或两次通过?

这是我的代码

public void atLast(int new_data)                             
{
    Node new_node=new Node(new_data);               
    if(head==null)                                  
    {
        head=new Node(new_data);
        return;
    }
    new_node.next=null;                              
    Node last=head;                                 
    while(last.next!=null)
    {
        last=last.next;
    }
    last.next=new_node;                             
    return;
}

Answer 1

如果这是你给面试官的代码，那么面试官一定是看错了，因为这是一次通过。

在您的情况下，"通过"将是您的while循环。它也可以通过递归、for或任何其他类型的循环来完成，这些循环遍历数组中的元素(或其他形式的项列表)。

在您的代码中，您运行Node列表并在末尾插入元素。这是在一个循环中完成的，使其成为一次循环。

现在来看一个两次传递的情况。例如，你被要求删除值最大的元素，并写了类似这样的东西:

int index = 0;
int count = 0;
int max = 0;
while(temp_node != null)
{
    if(temp_node.data > max)
    {
        index = count;
        max = temp_node.data;
    }
    count++;
    temp_node = temp_node.next;
}
for(int i = 0; i < count; i++)
{
    if(i == index)
    {
        //Functionality to remove node.
    }
}

第一次(while)检测值最大的Node。第二次遍历(for)通过再次遍历所有元素来删除这个Node，直到找到正确的元素。

Answer 2

我想这里的"两次遍历"意味着在代码中对整个列表迭代两次。在添加新节点时不需要这样做。