是比较两个节点然后删除 Θ(1) 的运行时间吗？

Question

所以问题中的数据结构是双向链表

假设我们需要比较 header 旁边节点的数据和预告片旁边节点的数据。然后，根据哪个节点的数据更大，我们删除数据更大的节点。

这整个过程是否占用了 Θ(1) 时间，还是比这更复杂？

Answer 1

是的，它是 O(1)，因为您直接访问头和尾。

Answer 2

过程的时间复杂度应该是O(1).

让我们看一个例子：

private void removeBiggerNode(LinkedList list) {
     ListNode currHead = list.head;
     ListNode currHeadNext = currHead.next;

     ListNode currTail = list.tail;
     currTailPrev = list.tail.previous;

     if(currHeadNext.val > currTailPrev.val) { 
        currHead.next = currHead.next.next;
        currHead.next.prev = currHead;
     }
     else { 
         tail.prev = tail.prev.prev;
         tail.prev.next = tail;
     }
}

ListNode 可以定义为：

public class ListNode {
    ListNode next;
    ListNode prev;
    int val;

    // constructor
    ListNode(int val){ this.val = val; }
}