不带头结点的链表创建

Question

算法实现在不带头节点的链表的第i-1(1≤i≤n+1)个结点后插入一个值为X的新结点，定义的函数头如下

LinkList *Insert( ElementType X, inti, LinkList *head )

Answer 1

基于Monster 组和GPT的调写：
用 C 语言实现在不带头节点的链表的第 i-1 (1 ≤ i ≤ n+1) 个结点后插入一个值为 X 的新结点的代码：

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};

typedef PtrToNode LinkList;

LinkList Insert(ElementType X, int i, LinkList head) {
    LinkList p, s;
    int j;
    p = head;
    j = 0;

    // 找到要插入位置的前一个结点
    while (p && j < i - 1) {
        p = p->Next;
        j++;
    }

    if (!p || j > i - 1) {  // 未找到位置或 i 的值不合法
        printf("Error: Invalid position\n");
        return NULL;
    }

    // 创建新结点并插入到链表中
    s = (LinkList)malloc(sizeof(struct Node));
    s->Data = X;
    s->Next = p->Next;
    p->Next = s;

    return head;  // 返回头结点
}

由于不带头结点的链表没有头指针，所以在函数的参数中需要传入头结点的指针，以便在插入新结点时可以正确地修改链表的指针关系。同时，在找到要插入位置的前一个结点后，需要判断 i 的值是否合法，即是否在 1~n+1 的范围内，如果不合法则返回 NULL。