基于链表的归并排序递归实现：如何跟踪链表尾节点？

递归实现的链表归并排序完全可以跟踪尾节点，你当前的问题是merge函数未正确赋值尾节点，且split_half未初始化子链表的size和tail属性，导致后续无法利用这些信息。

问题核心分析 #

1. merge函数尾节点未赋值：你代码中的merged_tail始终为NULL，没有通过递归逻辑确定尾节点，导致list->tail一直是无效值。
2. split_half未初始化子链表属性：拆分后的left和right链表只设置了head，size和tail仍为初始值，后续merge_sort无法正确维护这些属性。
3. merge参数未利用已排序链表信息：left和right经过merge_sort后已是有序链表，它们的tail是已知的，但你只传递了Node*类型的头节点，无法直接获取尾节点。

解决方案 #

方式一：递归merge配合指针参数传递尾节点 #

利用递归回溯特性，通过指针参数在递归调用中传递尾节点，终止时确定尾节点并回溯给上层调用。

修改后的核心代码：

// 递归merge，返回头节点，通过指针参数输出尾节点
Node* merge(Node* left, Node* right, Node** merged_tail) {
    if (left == NULL) {
        *merged_tail = right;
        if (*merged_tail != NULL) {
            while ((*merged_tail)->next != NULL) {
                *merged_tail = (*merged_tail)->next;
            }
        }
        return right;
    }
    if (right == NULL) {
        *merged_tail = left;
        while ((*merged_tail)->next != NULL) {
            *merged_tail = (*merged_tail)->next;
        }
        return left;
    }

    Node* merged_head;
    if (left->data <= right->data) {
        merged_head = left;
        merged_head->next = merge(left->next, right, merged_tail);
    } else {
        merged_head = right;
        merged_head->next = merge(left, right->next, merged_tail);
    }

    return merged_head;
}

// 修正split_half，初始化子链表的size、head、tail
void split_half(List* orig_list, List* left, List* right) { 
    Node* orig_head = orig_list->head;
    if (orig_head == NULL) {
        left->head = left->tail = NULL;
        left->size = 0;
        right->head = right->tail = NULL;
        right->size = 0;
        return;
    }
    if (orig_head->next == NULL) {
        left->head = left->tail = orig_head;
        left->size = 1;
        right->head = right->tail = NULL;
        right->size = 0;
        return;
    }
    Node* slow = orig_head, *fast = orig_head->next;
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }
    left->head = orig_head;
    left->tail = slow;
    left->size = (orig_list->size + 1) / 2;
    right->head = slow->next;
    slow->next = NULL;
    // 确定right的尾节点
    right->tail = right->head;
    if (right->tail != NULL) {
        while (right->tail->next != NULL) {
            right->tail = right->tail->next;
        }
    }
    right->size = orig_list->size / 2;
}

void merge_sort(List* list) {
    if (list->head == NULL || list->head->next == NULL) {
        // 单个节点或空链表，尾节点就是head
        list->tail = list->head;
        return;
    }
    List left = list_init, right = list_init;
    split_half(list, &left, &right);
    merge_sort(&left);
    merge_sort(&right);
    
    Node* merged_tail;
    list->head = merge(left.head, right.head, &merged_tail);
    list->tail = merged_tail;
    list->size = left.size + right.size;
}

方式二：利用已排序子链表的tail属性（迭代merge） #

因为left和right经过merge_sort后已是有序链表，它们的tail是已知的，直接基于这些信息确定合并后的尾节点，避免递归中额外遍历：

// 迭代merge，利用子链表的tail信息
void merge(List* dest, List* left, List* right) {
    dest->head = NULL;
    dest->tail = NULL;
    dest->size = left->size + right->size;

    Node* l_ptr = left->head;
    Node* r_ptr = right->head;

    while (l_ptr != NULL && r_ptr != NULL) {
        if (l_ptr->data <= r_ptr->data) {
            if (dest->head == NULL) {
                dest->head = l_ptr;
                dest->tail = l_ptr;
            } else {
                dest->tail->next = l_ptr;
                dest->tail = l_ptr;
            }
            l_ptr = l_ptr->next;
        } else {
            if (dest->head == NULL) {
                dest->head = r_ptr;
                dest->tail = r_ptr;
            } else {
                dest->tail->next = r_ptr;
                dest->tail = r_ptr;
            }
            r_ptr = r_ptr->next;
        }
    }

    // 处理剩余节点，直接复用子链表的tail
    if (l_ptr != NULL) {
        dest->tail->next = l_ptr;
        dest->tail = left->tail;
    }
    if (r_ptr != NULL) {
        dest->tail->next = r_ptr;
        dest->tail = right->tail;
    }
}

void merge_sort(List* list) {
    if (list->head == NULL || list->head->next == NULL) {
        list->tail = list->head;
        return;
    }
    List left = list_init, right = list_init;
    split_half(list, &left, &right);
    merge_sort(&left);
    merge_sort(&right);
    
    merge(list, &left, &right);
}

关键说明 #

• 两种方式都能正确维护链表的tail和size属性，后续可直接使用list->tail进行操作。
• 方式一保留递归merge逻辑，方式二用迭代merge更高效，且避免了额外的尾节点遍历。
• 必须修正split_half函数，为拆分后的子链表设置正确的size、head和tail，否则后续merge_sort无法正确维护这些属性。

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