如何减少代码中的双向链表复杂性

Question

// Complete the sortedInsert function below.

/*
 * For your reference:
 *
 * DoublyLinkedListNode {
 *     int data;
 *     DoublyLinkedListNode next;
 *     DoublyLinkedListNode prev;
 * }
 *
 */
static DoublyLinkedListNode sortedInsert(DoublyLinkedListNode head, int data) {
    DoublyLinkedListNode Leader=head;
    DoublyLinkedListNode newNode = new DoublyLinkedListNode(data);
    while(Leader.next!=null){

        if(data>Leader.data){
            Leader = Leader.next;
        } 
        else {
            if(Leader.prev == null) {
                newNode.next = Leader;
                Leader.prev = newNode;
                head = newNode;
                return head;
            } 
        }

    }
    if(Leader.next == null) {
        if(data<Leader.data) {
            newNode.prev = Leader.prev;
            newNode.next = Leader;
            Leader.prev.next = newNode;
            return head;
        } else {
            newNode.prev = Leader;
            Leader.next = newNode;
            return head;
        }


    }
       return head;



}

在上面排序的插入方法中如何减少这种双重链表复杂性，这是一个黑客问题，我正在为测试用例提供时间，我需要帮助来降低此代码的时间复杂度。

Answer 1

你的代码永远不会出现在while循环中。

让我们举个例子。 List = [（1），（4），（4）]（仅1个元素）。新节点是（4）。你的结果应该是[（1），（4），（4），（4）]。但是让我们走一下你的代码并检查会发生什么。最初的领导者=（1）

while(Leader.next!=null){ // 1

    if(data>Leader.data){  // 3
        Leader = Leader.next;
    } 
    else { // 6
        if(Leader.prev == null) { // 7
            newNode.next = Leader;
            Leader.prev = newNode;
            head = newNode;
            return head;
        } 
    }

}

在第1行检查将通过（as（1）.next不为null;实际上它是（4））。

在第3行（（4）>（1））。检查通行证。领导者=（1）.next =（4）。跳到第1行

在第1行检查将通过（as（4）.next不为null;实际上它是（4））。

在第3行（（4）>（4））。检查失败。输入第7行

在第7行检查将失败（（4）.prev不为空;实际上它是（4） - 第1 4）。 Leader中不会更新。领导者将保持不变，你将从这里进入infinte循环。

你将不得不照顾这个。也许问题的讨论页面会有所帮助。但是要试一试。

我自己的尝试包含在下面：

static DoublyLinkedListNode sortedInsert(DoublyLinkedListNode head, int data) {
        DoublyLinkedListNode n = new DoublyLinkedListNode();
        n.data = data;
        DoublyLinkedListNode curr = head;
        if (head == null) {
            return n;
        }
        // if given node is smaller than 1st node
        if (data < curr.data) {
            n.next = curr;
            return n;
        }
        // find first node greater than given node
        while (curr.next != null && curr.data < data) {
            curr = curr.next;
        }
        // reached to the end.
        if (curr.next == null && data >= curr.data) {
            curr.next = n;
        } else { // found the 1st node which is greater than given node
            curr.prev.next = n;
            n.next = curr;
        }
        return head;
    }