前言

向一个单向有序链表添加一个新的节点，这种问题记得在大学数据结构课上老师讲过好些次，都是进行分类处理，想到一步写一步，准确地阐释了所见即所想，所想即所写，所写即所得，这是一种试错的解题方法。 随后尝试了另外一种解题策略归纳总结，只需明确达到什么条件，向那个点插入即可。

链表数据结构与函数

链表的数据结构：

struct node
{
    struct node * next;    //连接链表的元素    
    int priority;          //优先级，此值越大越挂载链表的前面    
}

向链表添加一个新节点，要实现的函数：

//list - 需要操作的链表
//n    - 新节点
int AddNewNode(struct node **list, struct node *n);

试错方法

对于链表的添加进行一步一步的处理，分别对于头部添加，中部添加，尾部添加进行分类处理，如下所示：

• 源链表为空时，使头（*list）指向新出入的节点。
• 在第一个节点前加入，使头（*list）指向新插入的节点，新插入的节点n的next指向第一个节点。
• 在中间插入节点，首先新加入的节点的next执行当前插入位置节点，随后当前插入位置节点的前一个节点的next指向新节点n。
• 在尾部插入节点，使尾节点的next指向新节点，新节点n的next执行NULL。

对于这种方法的实现就不写了，我想大家都能够实现。

归纳总结方法

对插入的新节点，无非就是两个个地方的内存，用来存放新节点的地址（指向新节点），此处用存放更好理解，其两块内存如下所示：
第一个：是链表的最开头，*list这块内存，存放的地址是新节点地址。
第二个：是插入位置的上一个节点next这块内存，存放的地址是新节点地址。
所以只需要根据不同的条件移动list，使*list这块内存中，存放的是新节点的地址。

实现代码如下：

int AddNewNode(struct node **list, struct node *n);
{
    while(*list)
    {
        if(n->priority > (*list)->priority);
            break;
        list = &((*list)->next);
    }
    n->next = *list;
    *list = n;

    return 0;
}

总结：不要寻思新节点要挂载到那个节点的next下，而是要认清事物的本质，究竟是要把新节点的指针写入那块内存。

转载请注明：HunterYuan的博客 » 向有序单向链表添加新的节点