在排序的双链表中插入

Question

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

示例输入

NULL, data = 2

零& lt;, 2 & lt;——> 4 & lt; -> 6 -> NULL, data = 5

的示例输出

NULL <——2 -> NULL

零& lt;, 2 & lt;——> 4 & lt;——> 5 & lt;零-> 6 ->

我尝试了上面的问题。但是我的程序因超时而终止。我在下面的代码做错了什么。假设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;   
}

Answer 2

如果头部节点为空，则在尝试获取下一个/前一个节点时将获得NullPointerException。你应该先检查一下:

Node sortedInsert(Node head, int data) {
    Node newn = new Node();
    newn.data = data;
    //Basic case: the list is empty, so the head is null
    if (head==null) {
        return newn;
    }
    //If node is not null
    Node aux= head;
    Node auxPrev;
    while (aux!=null && aux.data<data) {
        auxPrev=aux;
        aux=aux.next;
    }
    //auxPrev will be null if we are going to insert in the first position
    if (auxPrev!=null)
        auxPrev.next=newn;
        newn.prev=auxPrev;
        head=newn;
    }
    //aux will be null if we insert in the last position
    if (aux!=null) {
        aux.prev=newn;
        newn.next=aux;
    }
    return head;
}