LeetCode合并两个有序链表：代码超时(TLE)原因咨询及哨兵节点实现需求

嘿，我帮你定位到代码的问题啦！你的合并有序链表代码出现超时（TLE）的核心原因是哨兵节点head未被正确初始化，它是一个野指针，直接操作node->next会引发未定义行为，导致程序陷入异常循环或内存访问错误，最终触发超时。

具体问题点 #

你声明了struct ListNode *head;但没有为它分配内存或指向一个有效的节点，此时head是一个随机指向内存中某个位置的野指针。当你执行struct ListNode *node = head;后，node同样是野指针，后续对node->next的赋值操作完全非法——这会破坏未知内存区域的数据，操作系统可能会拦截该操作，或者程序进入不可控的死循环状态，表现为超时。

修复后的代码 #

我们需要为哨兵节点head分配一个实际的空节点（哑节点），作为合并链表的起始锚点，这样后续的指针操作就有了合法的起始位置。同时还可以优化剩余链表的拼接逻辑（无需循环逐个添加，直接指向剩余链表头即可）：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    // 初始化哨兵节点（哑节点），分配内存确保指针有效
    struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode *node = head;
    // 处理两个链表都为空的情况
    if(!list1 && !list2){
        free(head); // 避免内存泄漏
        return NULL;
    }
    while(list1 && list2){
        if(list1->val < list2->val){
            node->next = list1;
            list1 = list1->next;
        } else{
            node->next = list2;
            list2 = list2->next;
        }
        node = node->next;
    }
    // 拼接剩余链表，无需循环，直接指向剩余链表头即可
    if(list1){
        node->next = list1;
    }
    if(list2){
        node->next = list2;
    }
    // 保存合并后的链表头，然后释放哨兵节点避免内存泄漏
    struct ListNode *result = head->next;
    free(head);
    return result;
}

关键修复说明 #

• 初始化哨兵节点：用malloc为head分配内存，确保它是一个有效的节点指针，后续的node->next操作才有合法的内存空间。
• 内存泄漏处理：最后要释放哨兵节点的内存，避免长期运行导致内存泄漏。
• 优化剩余链表拼接：当其中一个链表遍历完后，直接将剩余链表的头节点挂到当前node的next上即可，无需逐个节点遍历，提升代码效率。
• 保留原链表头节点：整个过程中只是将原链表的节点链接到新的合并链表中，没有修改原链表的头节点值或指向，完全符合你的需求。

内容的提问来源于stack exchange，提问作者周志桓