C语言：仅移动指针合并有序链表至list1（问题排查）

现有两个已排序链表list1和list2，目标是将list2合并到list1中，需满足以下要求：

• 结果链表必须为list1，不得新建链表存储合并结果；
• 函数返回类型必须为void；
• 合并完成后list2需为空；
• 合并后的链表必须保持有序；
• 仅允许移动指针，不得删除或移除任何节点；
• 禁止使用递归；
• 算法中不允许执行排序操作；
• 不得使用其他辅助函数。

示例输入 #

• list1: d -> e -> f -> t -> w -> x -> y -> NULL
• list2: a -> b -> e -> j -> l -> z -> NULL

预期结果 #

• list1: a -> b -> d -> e -> e -> f -> j -> l -> t -> w -> x -> y -> z -> NULL
• list2: empty

当前代码运行结果 #

• list1: d -> e -> f -> j -> l -> t -> w -> x -> y -> z -> NULL
• list2: a -> b -> d -> e -> e -> f -> j -> l -> t -> w -> x -> y -> z -> NULL

当前代码 #

typedef struct listNode {
        char data;
        struct listNode* nextPtr;
} ListNode;
        
typedef ListNode* ListNodePtr;


void mergeSortedList(ListNodePtr list1, ListNodePtr list2) {

    ListNodePtr curr = NULL;
    ListNodePtr last = NULL;

    if (list1->data < list2->data)
    {
        curr = list1;
        last = list1;
        list1 = list1->nextPtr;
    }
    else {
        curr = list2;
        last = list2;
        list2 = list2->nextPtr;
    }
    last->nextPtr = NULL;

    while (list1 != NULL && list2 != NULL) {
        if (list1->data < list2->data) {
            last->nextPtr = list1;
            last = list1;
            list1 = list1->nextPtr;
        }
        else {
            last->nextPtr = list2;
            last = list2;
            list2 = list2->nextPtr;
        }
        last->nextPtr = NULL;
    }

    if (list1 != NULL) {
        last->nextPtr = list1;
    }
    else {
        last->nextPtr = list2;
    }
}

1. 参数传递错误：原函数参数为值传递，修改内部的list1和list2指针不会影响外部的链表头，导致无法将list2的头节点设为list1的新头，也无法最终清空list2。
2. 错误截断链表：每次执行last->nextPtr = NULL会破坏原链表的连续结构，导致list1的后续节点丢失。
3. 未关联结果到原list1：内部创建的curr指针存储了合并后的头，但未赋值给外部的list1，导致外部list1仍为原头节点。
4. 边界场景未处理：未考虑list1为空的情况，也未在合并后将list2置空。

typedef struct listNode {
        char data;
        struct listNode* nextPtr;
} ListNode;
        
typedef ListNode* ListNodePtr;


void mergeSortedList(ListNodePtr *list1, ListNodePtr *list2) {
    // 处理list1为空的情况，直接将list2全部移到list1
    if (*list1 == NULL) {
        *list1 = *list2;
        *list2 = NULL;
        return;
    }

    ListNodePtr prev = NULL;
    ListNodePtr curr1 = *list1;
    ListNodePtr curr2 = *list2;

    // 遍历list2的每个节点，插入到list1的合适位置
    while (curr2 != NULL) {
        // 找到list1中第一个大于等于curr2->data的节点的前一个位置
        while (curr1 != NULL && curr1->data < curr2->data) {
            prev = curr1;
            curr1 = curr1->nextPtr;
        }

        // 保存list2的下一个节点
        ListNodePtr next2 = curr2->nextPtr;

        // 将curr2插入到list1的对应位置
        if (prev == NULL) {
            // 插入到list1的头部
            *list1 = curr2;
        } else {
            // 插入到prev和curr1之间
            prev->nextPtr = curr2;
        }
        curr2->nextPtr = curr1;

        // 更新指针，继续处理下一个list2节点
        prev = curr2;
        curr2 = next2;
    }

    // 将list2置空
    *list2 = NULL;
}

1. 修改参数类型：改用指针的指针传递，直接修改外部的链表头指针，满足合并结果为list1、list2为空的要求。
2. 遍历插入逻辑：逐个遍历list2节点，在list1中找到合适插入位置，仅通过移动指针完成插入，不修改节点数据或新建节点。
3. 边界处理：list1为空时直接接管list2所有节点；插入到list1头部时更新头指针。
4. 清空list2：合并完成后将*list2置为NULL，确保list2为空。
5. 保留原结构：通过追踪prev和curr1指针，避免截断原链表，维护链表连续性。

内容的提问来源于stack exchange，提问作者DanCode