526互联

论单向链表有序插入方案

发布时间 2023-03-22 21:42:46作者: Qing-Huan

0. 思考

单向链表有序插入，插入点分为这样几个地方：

  1. 当前链表为空，被插入节点是第一个节点
  2. 被插入节点作为头结点
  3. 被插入节点在中间
  4. 被插入节点在尾部

那么按照这样的步骤一步步的去实现，需要两个指针，后指针作为比较节点，前指针仅是为了记录位置，便于链表节点在中、尾两处插入。

1. 单指针记录遍历

如果转换一下思路，一前一后两个指针一直是相邻的，那是否不需要前指针记录位置了呢？
若当前情况，不属于空链表和头插入，那我可以用 node->next 节点与被插入节点进行比较，直到 node->next 节点为空

image

2. 抽象合并优化

可以看到链表为空的情况和头插入情况，唯一相差的是：

  • 链表不为空时，被插入节点指向头结点 pi->next = head;
  • 链表为空时，被插入节点指向NULL，那么此时头结点刚刚好也是空，也满足 pi->next = head(NULL);

====> 被插入节点终将都是头结点

  • 中间插入时，被插入节点要指向 pb->next
  • 尾部插入时，被插入节点要指向空，那么此时 pb->next 也为空

====> 将尾结点指向的NULL，看成是一个没有数据域且指针域为空的节点

STU* insert_link(STU* head, STU tmp)
{
    STU* prev = NULL;
    STU* pb = head;
    for(; NULL != pb && pb->num < tmp.num; pb = pb->next)
    {
        prev = pb;
    }

    STU* pi = (STU*)calloc(1, sizeof(STU));
    *pi = tmp;
    pi->next = NULL;

    if(NULL == prev)
    {
        pi->next = head;
        head = pi;
    }
    else
    {
        pi->next = prev->next;
        prev->next = pi;
    }
    return head;
}