java - 插入已排序的双向链表

Question

我得到了一个指向已排序双向链表的头节点的指针和一个要插入到列表中的整数。我被告知创建一个节点并将其插入到列表中的适当位置，使其排序顺序为保持。头节点可能为 NULL。

示例输入

NULL，数据=2

NULL <-- 2 <--> 4 <--> 6 --> NULL，数据 = 5

示例输出

NULL <-- 2 --> NULL

NULL <-- 2 <--> 4 <--> 5 <--> 6 --> NULL

我尝试了上述问题。但是我的程序由于超时而终止。下面的代码中我做错了什么。假设 Node 类和 main 函数已经存在。非常感谢!

Node SortedInsert(Node head,int data) {

    Node newn = new Node();

    newn.data = data;
    newn.prev=null;
    newn.next = null;

    Node ptr = head;
    Node nex=head.next;

    while(ptr!=null && nex!=null) {
        if(ptr.data<=newn.data && nex.data>=newn.data) {
            newn.next = nex;
            newn.prev = ptr;
            nex.prev = newn;
            ptr.next = newn;
        }            
        else {
            nex=nex.next;
            ptr=ptr.next;
        }
    }

    if(ptr!=null && nex==null) {
        if(ptr.data>=newn.data) {
            newn.next=ptr;
            ptr.prev=newn;
            newn.prev=null;
            head=newn;
        }
        else {
            ptr.next=newn;
            newn.prev = head;
        }
    }

    if(head==null) {
        head = newn; 
    }

    return head;

}

Answer 1

相当简单:成功插入后，您不会跳出循环。因此它会在插入节点的位置上不断循环。做一个微小的改变:

if(ptr.data>=newn.data)
{
    newn.next=ptr;
    ptr.prev=newn;
    newn.prev=null;
    head=newn;
    break;
}

但是，您编写了一些冗余代码。这更短并且不包含冗余代码:

Node SortedInsert(Node head,int data) {

    Node newn = new Node();
    newn.data = data;  

    Node ptr = head;

    if (ptr == null) {
        head = newn;

    } else if ( ptr.data > newn.data ) {
        newn.next = ptr;
        ptr.prev = newn;
        head = newn;

    } else {
        Node nex = head.next;

        while (nex != null && nex.data <= newn.data) {
            ptr = nex;
            nex = nex.next;
        }

        ptr.next = newn;
        newn.prev = ptr;

        if (nex != null) {
            nex.prev = newn;
            newn.next = nex;
        }
    }

    return head;   
}