给定一个排序的链表和要插入的值，编写一个函数以排序的方式插入值

Question

下面的代码执行但有时它不会在某些已排序的位置添加...

This image显示给定链表和插入新元素后的链表

有人可以帮我解决这个问题吗？

void insert()
{
    p=(NODE *)malloc(sizeof(NODE));
    printf("\nEnter data to add : ");
    scanf("%d",&p->data);
    if(start==NULL)
    {
        start=p;
        p->next=NULL;
    }
    else
    {
        q=start;
        if(q->data > p->data)
        {
            p->next=start;
            start=p;            
        }
        else
        {
            while(p->data > q->data && q->next!=NULL)
            {
                r=q;
                q=q->next;
            }
                q->next=p;
                p->next=NULL;
            }
        }
    }
}

Answer 1

您的代码的问题是您要么在列表末尾插入 NODE，要么在某个特定点插入节点并删除其余节点，而不管它们的值如何。

更改了 else 部分（当当前节点数据大于根节点数据时），如下所示：

 while(p->data > q->data && q->next!=NULL)
 {
     r=q;
     q=q->next;
 }
   
 // r- is the just previous node of the place where new node needs to be inserted.

if(q->next == NULL)
{
    q->next = p; 

   /* this block is the end position of linked list in other words no place found
      where we can insert a node, for example if your list is 1->5->7->11 and
      you want to insert 15, then you need to insert node at the end */
}
else
{
    r->next = p;
    p->next = q;
   /* this is interesting part, r - is the node after which we want to insert new node. 

      so, r->next = p -- actually holds new node after r which p,
      and p->next = q -- holds remaining nodes of linked list.
      
      for example, think, initially your list was:
      3->6->9->11->15 and you want to insert 8, in this case

      r (3, 6) -> next = p (8);
      p (8) -> next = q (9, 11, 15);
      so finally we will get: 3->6->8->9->11->15
    */
}

Answer 2

在 else 部分中分配值只是一个小的变化。您在循环中使用了 r 但之后从未使用过它。这是更正后的代码，仅更改了 while 循环条件并在之后进行分配。

void insert()
{
    p=(NODE *)malloc(sizeof(NODE));
    printf("\nEnter data to add : ");
    scanf("%d",&p->data);
    if(start==NULL)
    {
        start=p;
        p->next=NULL;
    }
    else
    {
        q=start;
        if(q->data > p->data)
        {
            p->next=start;
            start=p;
        }
        else
        {   
            while(q!=NULL && p->data >= q->data)
            {
                r=q;
                q=q->next;
            }
            r->next=p;
            p->next=q;
        }
    }
}

给定一个排序的链表和要插入的值，编写一个函数以排序的方式插入值

Given a sorted linked list and value to insert, write a function to insert the value in sorted way

c

linked-list

insert

data-structures

singly-linked-list