search - 是时候找到链表中的最大元素了

Question

我有一个有序链表。我想知道在这两种情况下找到最大元素的时间:

• 如果我维护一个指向链表末尾的尾指针，并且
• 如果我不这样做。

Answer 1

对于有序链表:

• O(1) 如果列表是从最大到最小排序的，因为第一个已经是最大的。

• O(n) 如果列表是从 min 到 max 排序的，如果你进一步有尾指针，它将变成 O(1)。原因是最大元素是链表中的最后一个。因此，您必须遍历到尾部 (O(n))。另一方面，当你有尾指针时，这将是 O(1)，你只需返回尾指针指向的内容。

对于无序链表:

• 总是 O(n) 不管你有没有尾指针。原因是，对于一个无序的线性列表，你必须遍历(O(n))每一个来确定哪个是最大的。即使使用尾指针也无济于事。