是时候找到链接列表中的最大元素了

Question

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

• 如果我保持指向链表末尾的尾指针,和
• 如果我不这样做.

Answer 1

对于有序链表:

• O(1) 如果列表从max到min排序,因为第一个已经是最大值.

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

对于未排序的链表:

• 总是O(n)不管你有没有尾指针.原因是,对于无序排列的列表,您必须遍历(O(n))每个列表以确定哪一个是最大值.即使使用尾指针也无济于事.