C语言链表合并报错：成员访问地址未对齐问题排查

问题背景 #

我在解决LeetCode 23题《合并K个有序链表》时遇到了运行时错误，题目要求如下：

给定一个由k个有序链表组成的数组lists，每个链表均按升序排列。
将所有链表合并为一个升序链表并返回。
约束条件：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i]按升序排列。
• 所有lists[i].length的总和不超过10^4。

提交代码后出现以下运行时错误：

Line 70: Char 15: runtime error: member access within misaligned address 0x7fc00000000c for type 'struct ListNode', which requires 8 byte alignment [ListNode.c]
0x7fc00000000c: note: pointer points here
<memory cannot be printed>

我提交的代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if (list1==NULL && list2==NULL)
        return NULL;
    struct ListNode head  ;
    struct ListNode *result = &head;
    while (list1 && list2) {
       if (list1->val < list2->val) {
           result->next=list1;
           list1=list1->next;
           result = result->next;
       }
       else {
           result->next=list2;
           list2=list2->next;
           result = result->next;
       }
    }
    if (list1) {
        result->next=list1;
    }
    if (list2) {
        result->next=list2;
    }
    return head.next;
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize)
{
   struct ListNode head;
   struct ListNode *result = &head;
   result=mergeTwoLists(lists[0],lists[1]);
   for (int i = 2; i<listsSize; i++) {
       result=mergeTwoLists(result,lists[i]);
   }
   return head.next;
}

错误原因分析 #

核心问题出在mergeKLists函数中：

1. 多余且未初始化的栈变量head：你在函数里声明了栈上的struct ListNode head，但之后完全没有给它的next成员赋值，head的内存处于未初始化状态，里面是随机的垃圾值。
2. 错误返回未初始化的head.next：你最后返回的是head.next，这个值是一个随机的垃圾地址。而struct ListNode要求8字节对齐（64位系统下指针成员占8字节），这个随机地址大概率不符合对齐要求，因此触发了内存对齐错误。
3. 边界情况未处理：当listsSize为0或1时，直接访问lists[0]或lists[1]会导致数组越界，但这里的对齐错误主要由前面的问题引发。

另外，mergeTwoLists函数的实现是没问题的：它用栈上的head作为哨兵节点，最后返回的head.next指向原链表的有效堆内存节点，函数返回后栈上的head销毁不影响返回的链表。

修正方案 #

移除mergeKLists中多余的head变量，直接返回合并后的result，同时处理边界情况：

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize)
{
    if (listsSize == 0) return NULL;
    if (listsSize == 1) return lists[0];
    struct ListNode *result = mergeTwoLists(lists[0], lists[1]);
    for (int i = 2; i < listsSize; i++) {
        result = mergeTwoLists(result, lists[i]);
    }
    return result;
}

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