双向链表归并排序：如何正确设置prev指针？

你卡在双向链表归并排序的prev指针设置上太正常了——你的现有代码是完全基于单向链表实现的，所有操作只维护了next指针，完全没考虑双向链表必需的双向关联逻辑。咱们一步步把prev指针的处理补全，让整个归并排序适配双向链表。

问题根源 #

单向链表的归并排序只需要处理节点的next指向，但双向链表要求每个节点的prev和next必须同时保持合法关联。你之前单独设置back->prev = NULL这类操作只处理了单个节点，没有在合并的每一步同步维护双向指针，自然会出现关联断裂的问题。

1. 修正Split函数（拆分边界的双向处理） #

原拆分函数只断开了next指针，现在需要在拆分时同步处理第二个链表头节点的prev，确保两个拆分后的链表都是合法的双向链表：

void split(node *head, node **front, node **back) {
    node *slow, *fast;
    if (head == NULL || head->next == NULL) {
        *front = head;
        *back = NULL;
    } else {
        slow = head;
        fast = head->next;
        while (fast != NULL) {
            fast = fast->next;
            if (fast != NULL) {
                slow = slow->next;
                fast = fast->next;
            }
        }
        *front = head;
        *back = slow->next;
        // 关键：处理双向链表的拆分边界
        if (*back != NULL) {
            (*back)->prev = NULL; // 第二个链表的头节点prev置空
        }
        slow->next = NULL; // 断开第一个链表的尾部
    }
}

这里的核心是：拆分后第二个链表的头节点必须和原链表断开prev关联，否则会出现跨链表的无效指针。

2. 核心修正：Merge函数（同步维护双向指针） #

原合并函数只处理了next，现在要在每一步链接节点时，同步设置新节点的prev指针，确保双向关联：

void merge(node **head, node *l1, node *l2) {
    node *newHead = NULL;
    node *curr = NULL;

    if (l1 == NULL) {
        newHead = l2;
    } else if (l2 == NULL) {
        newHead = l1;
    } else {
        // 确定合并后的头节点，同步设置prev
        if (l2->key < l1->key) {
            newHead = l2;
            l2 = l2->next;
        } else {
            newHead = l1;
            l1 = l1->next;
        }
        curr = newHead;
        curr->prev = NULL; // 头节点的prev必须为空

        // 逐节点合并，同步维护双向指针
        while (l1 != NULL && l2 != NULL) {
            if (l2->key < l1->key) {
                curr->next = l2;
                l2->prev = curr; // 让新节点的prev指向当前节点
                l2 = l2->next;
            } else {
                curr->next = l1;
                l1->prev = curr; // 同样设置双向关联
                l1 = l1->next;
            }
            curr = curr->next;
        }

        // 处理剩余节点，同步补全prev
        if (l1 != NULL) {
            curr->next = l1;
            l1->prev = curr;
        }
        if (l2 != NULL) {
            curr->next = l2;
            l2->prev = curr;
        }
    }

    *head = newHead;
}

这里的关键逻辑是：每次将节点接到当前链表尾部时，必须同时让该节点的prev指向当前尾部节点，这样才能保证双向链表的完整性，而不是只修改next指针。

3. MergeSort函数无需修改 #

原递归逻辑是通用的，只负责拆分和合并的调度，不需要直接处理指针，保持原样即可：

void mergeSort(node **head) {
    node *h1 = NULL;
    node *h2 = NULL;
    if((*head) != NULL && (*head)->next != NULL) {
        split((*head),&h1,&h2);
        mergeSort(&h1);
        mergeSort(&h2);
        merge(head,h1,h2);
    }
}

验证工具（可选） #

可以写一个打印函数，同时输出每个节点的prev和next关联，方便调试：

void printDoubleList(node *head) {
    node *curr = head;
    while (curr != NULL) {
        printf("Key: %d | ", curr->key);
        if (curr->prev) printf("Prev: %d | ", curr->prev->key);
        else printf("Prev: NULL | ");
        if (curr->next) printf("Next: %d\n", curr->next->key);
        else printf("Next: NULL\n");
        curr = curr->next;
    }
}

总结一下：双向链表的归并排序核心就是在所有修改next指针的操作中，同步修改对应的prev指针，确保每个节点的前后关联都被正确维护，而不是孤立地调整某个节点的指针。

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