将链表递归归并排序转换为基于栈的迭代实现

一、先修正递归实现中的关键bug #

你的递归代码存在几个致命问题，不修正的话迭代实现也无法正确工作：

1. list_split参数传递错误：函数接收list_t *l1、list_t *l2是传值调用，内部给l1赋值不会修改外部变量，需要改为传指针的指针list_t **l1、list_t **l2。
2. list_split逻辑错误：开头判断l->next是非法的（l是list_t*，没有next成员），应该判断l->first == NULL || l->first->next == NULL。
3. list_merge定义与调用不符：递归函数中调用return list_merge(l1, l2)，但list_merge是void类型，无返回值，需要调整为返回合并后的有序链表。
4. 缺少create_node实现：list_push_back依赖该函数，需补充实现。

修正后的递归代码示例：

#include <stdlib.h>

typedef int element_t;
typedef struct node_s* node_t;

struct node_s {
    element_t data;
    node_t next;
};

typedef struct list_s list_t;
struct list_s {
    node_t first;
    node_t last;
};

node_t create_node(element_t data) {
    node_t n = malloc(sizeof(struct node_s));
    if (!n) return NULL;
    n->data = data;
    n->next = NULL;
    return n;
}

list_t* empty_list() {
    list_t* l = malloc(sizeof(list_t));
    if (!l) return NULL;
    l->first = l->last = NULL;
    return l;
}

void list_push_back(element_t elm, list_t *l) {
    node_t cur = create_node(elm);
    if (!cur) return;
    if (!l->first) {
        l->first = cur;
    } else {
        l->last->next = cur;
    }
    l->last = cur;
}

void list_split(list_t *l, list_t **l1, list_t **l2) {
    if (!l || !l->first || !l->first->next) {
        *l1 = l;
        *l2 = NULL;
        return;
    }

    node_t slow = l->first;
    node_t fast = l->first->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    *l1 = empty_list();
    (*l1)->first = l->first;
    (*l1)->last = slow;

    *l2 = empty_list();
    (*l2)->first = slow->next;
    (*l2)->last = l->last;

    slow->next = NULL;
}

list_t* list_merge(list_t *l1, list_t *l2) {
    if (!l1 || !l1->first) return l2;
    if (!l2 || !l2->first) return l1;

    list_t *merged = empty_list();
    node_t p1 = l1->first;
    node_t p2 = l2->first;

    while (p1 && p2) {
        if (p1->data <= p2->data) {
            list_push_back(p1->data, merged);
            p1 = p1->next;
        } else {
            list_push_back(p2->data, merged);
            p2 = p2->next;
        }
    }

    while (p1) {
        list_push_back(p1->data, merged);
        p1 = p1->next;
    }
    while (p2) {
        list_push_back(p2->data, merged);
        p2 = p2->next;
    }

    free(l1);
    free(l2);
    return merged;
}

list_t* list_merge_sort(list_t *l) {
    if (!l || !l->first || !l->first->next) {
        return l;
    }

    list_t *l1, *l2;
    list_split(l, &l1, &l2);
    l1 = list_merge_sort(l1);
    l2 = list_merge_sort(l2);
    return list_merge(l1, l2);
}

二、你的迭代实现思路分析：不正确 #

当前迭代代码存在核心逻辑错误：

1. 栈的使用逻辑错误：归并排序需要先拆分到单个节点（最小有序单元），再从底向上合并相邻有序链表；而你拆完就直接合并未排序的子链表，完全不符合分治顺序。
2. 变量与返回逻辑错误：循环中return l会直接终止函数，栈中剩余元素无法处理；内部重新定义的list_t *l会覆盖外部参数，导致内存混乱。
3. 缺少状态标记：栈中只存头节点，无法区分链表是否已拆分排序，无法模拟递归的回溯合并过程。

三、正确的基于栈的迭代归并排序思路 #

栈需要存储待处理链表片段和状态标记（未拆分/已排序待合并/合并触发标记），模拟递归的调用流程：

1. 定义栈元素结构，包含链表指针和状态标记。
2. 初始将整个链表以未拆分状态入栈。
3. 循环处理栈：
   • 弹出未拆分且长度>1的链表，拆分后先入栈右子链表（未拆分）、再左子链表（未拆分），最后入栈合并标记。
   • 弹出已排序的链表，暂存等待合并。
   • 弹出合并标记时，取出两个暂存的已排序链表，合并后将新链表以已排序状态入栈。
4. 最终栈中剩余的唯一元素就是排序完成的链表。

四、完整的基于栈的迭代实现代码 #

#include <stdlib.h>

// 复用修正后的链表结构定义（node_t、list_t、create_node、empty_list等）

typedef struct stack_item_s {
    list_t *list;
    int is_sorted; // 0=未拆分, 1=已排序待合并, -1=合并标记
} stack_item_t;

typedef struct stack_s {
    stack_item_t *items;
    int top;
    int capacity;
} stack_t;

stack_t* create_stack(int capacity) {
    stack_t *s = malloc(sizeof(stack_t));
    if (!s) return NULL;
    s->items = malloc(sizeof(stack_item_t) * capacity);
    if (!s->items) {
        free(s);
        return NULL;
    }
    s->top = -1;
    s->capacity = capacity;
    return s;
}

int is_empty(stack_t *s) {
    return s->top == -1;
}

int push(stack_t *s, stack_item_t item) {
    if (s->top >= s->capacity - 1) return 0;
    s->items[++s->top] = item;
    return 1;
}

stack_item_t pop(stack_t *s) {
    stack_item_t empty = {NULL, 0};
    if (is_empty(s)) return empty;
    return s->items[s->top--];
}

int list_length(list_t *l) {
    int len = 0;
    node_t p = l->first;
    while (p) {
        len++;
        p = p->next;
    }
    return len;
}

list_t* list_iter_merge_sort(list_t *l) {
    if (!l || !l->first || !l->first->next) {
        return l;
    }

    int len = list_length(l);
    stack_t *s = create_stack(len * 2);
    if (!s) return l;

    stack_item_t initial = {l, 0};
    push(s, initial);

    list_t *temp1 = NULL, *temp2 = NULL;

    while (!is_empty(s)) {
        stack_item_t item = pop(s);

        if (item.is_sorted == -1) {
            if (temp1 && temp2) {
                list_t *merged = list_merge(temp1, temp2);
                stack_item_t merged_item = {merged, 1};
                push(s, merged_item);
                temp1 = temp2 = NULL;
            }
        } else if (item.is_sorted == 1) {
            if (!temp1) {
                temp1 = item.list;
            } else {
                temp2 = item.list;
                stack_item_t merge_mark = {NULL, -1};
                push(s, merge_mark);
            }
        } else {
            list_t *cur_list = item.list;
            if (!cur_list || !cur_list->first || !cur_list->first->next) {
                stack_item_t sorted_item = {cur_list, 1};
                push(s, sorted_item);
                continue;
            }

            list_t *l1, *l2;
            list_split(cur_list, &l1, &l2);
            free(cur_list);

            stack_item_t right_item = {l2, 0};
            push(s, right_item);
            stack_item_t left_item = {l1, 0};
            push(s, left_item);
            stack_item_t merge_mark = {NULL, -1};
            push(s, merge_mark);
        }
    }

    stack_item_t result = pop(s);
    free(s);
    return result.list;
}

关键说明 #

• 栈通过先入右子链表、再左子链表、最后合并标记的顺序，保证合并时左右子链表已完成排序，完全模拟递归的分治流程。
• 状态标记区分不同类型的栈元素，确保合并操作仅在两个有序链表间进行。
• 可根据需求调整内存释放逻辑，避免内存泄漏。

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