时间戳

首页 > 解决方案 > 按顺序将节点插入到排序的双向链表中

c++ - 按顺序将节点插入到排序的双向链表中

问题描述

我有将节点插入链表的代码。要求是代码从输入中消除重复项，并将它们按顺序排列。它通过了多个测试用例，但不是全部。如果有人有任何见解，那将非常有帮助。谢谢。

DoublyLinkedListNode* sortedInsert(DoublyLinkedListNode* head, int data){

    DoublyLinkedListNode* temp = new DoublyLinkedListNode(data);

    if (head == NULL)  
    {   
        return temp;   
    }

    if (head->data == data)  
    {  
        return head;  
    }

    if (head->data > data)   
    {   
         temp->next = head;          
         return temp;   
    }

    if(head->next != NULL)  
    {    
         head->next = sortedInsert(head->next, data);   
    }

    else  
    {       
        head->next = temp;  
    }

    return head;

}

标签： c++insertnodes

解决方案

Whole your function can be written as:

DoublyLinkedListNode* sortedInsert(DoublyLinkedListNode* head, int data)
{
    if( head and head->data <= data ) {
        if( head->data < data ) 
           head->next = sortedInsert(head->next, data);
        return head;
    }
    DoublyLinkedListNode* temp = new DoublyLinkedListNode(data);
    temp->next = head;
    return temp;
}

it is shorter, simpler and does not have memory leak. Btw it is usually not a good idea to call single linked list node as DoublyLinkedListNode and also it is not a good idea to return raw pointer to dynamically allocated memory, use a smart pointer instead.

推荐阅读