C语言链表分区问题

C语言链表分区问题

在链表相关的问题中，分区问题是一个典型的算法场景。本文将以 partition 函数为例，讲解如何实现将链表分为两部分，其中一部分的节点值小于指定值 $x$，另一部分的节点值大于或等于 $x$。

---

问题描述

给定一个单链表和一个值 $x$，我们需要重新排列链表，使得：

• 所有小于 $x$ 的节点位于链表前部分；
• 所有大于或等于 $x$ 的节点位于链表后部分；
• 两部分中的节点相对顺序保持不变。

例如：
输入链表为：
$$1\to 4\to 3\to 2\to 5\to 2$$
分区值为 $x=3$，则输出为：
$$1\to 2\to 2\to 4\to 3\to 5$$

---

分析与实现

核心思路

1. 使用两个虚拟链表：
   • 一个链表 small 保存所有小于 $x$ 的节点；
   • 一个链表 big 保存所有大于或等于 $x$ 的节点。
2. 遍历原链表：
   • 对每个节点，根据其值将其添加到 small 或 big 链表中。
3. 拼接链表：
   • 将 small 链表的尾部与 big 链表的头部相连。
4. 返回结果：
   • 返回新的链表头。

代码实现

以下是具体代码实现：

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* partition(struct ListNode* head, int x) {
    // 创建两个虚拟头节点
    struct ListNode* small = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* big = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* temp_small = small;
    struct ListNode* temp_big = big;

    // 初始化虚拟链表
    small->next = NULL;
    big->next = NULL;

    // 遍历原链表
    while (head != NULL) {
        if (head->val < x) {
            // 创建新节点并添加到 small 链表
            temp_small->next = (struct ListNode*)malloc(sizeof(struct ListNode));
            temp_small = temp_small->next;
            temp_small->val = head->val;
        } else {
            // 创建新节点并添加到 big 链表
            temp_big->next = (struct ListNode*)malloc(sizeof(struct ListNode));
            temp_big = temp_big->next;
            temp_big->val = head->val;
        }
        head = head->next;
    }

    // 结束 big 链表
    temp_big->next = NULL;

    // 拼接 small 和 big 链表
    temp_small->next = big->next;

    // 释放 big 的头节点
    free(big);

    // 返回新链表的头节点
    struct ListNode* result = small->next;
    free(small);
    return result;
}

---

详细解释

虚拟头节点的作用

虚拟头节点的引入使得链表操作更为简洁，避免了单独处理链表头的复杂逻辑。以下是两个虚拟头节点的初始化：

struct ListNode* small = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* big = (struct ListNode*)malloc(sizeof(struct ListNode));
small->next = NULL;
big->next = NULL;

虚拟头节点使得我们可以从任意位置开始构建链表，而无需额外判断是否是第一个节点。

---

遍历原链表

通过遍历原链表，将节点分配到对应的 small 或 big 链表中：

while (head != NULL) {
    if (head->val < x) {
        temp_small->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        temp_small = temp_small->next;
        temp_small->val = head->val;
    } else {
        temp_big->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        temp_big = temp_big->next;
        temp_big->val = head->val;
    }
    head = head->next;
}

在每次分配时，记得使用 malloc 创建新的节点，否则会破坏链表的结构。

---

拼接链表

完成遍历后，将 small 和 big 两部分链表拼接起来：

temp_big->next = NULL;      // 确保 big 链表以 NULL 结尾
temp_small->next = big->next; // 拼接 small 和 big 链表
free(big);                  // 释放 big 的虚拟头节点

注意在拼接之前，我们需要确保 big 链表以 NULL 结尾。

---

内存管理

在使用动态内存分配时，要注意避免内存泄漏。本文代码在最后释放了 small 和 big 的虚拟头节点：

struct ListNode* result = small->next; // 获取结果链表
free(small);                          // 释放虚拟头节点
return result;

---

时间与空间复杂度

1. 时间复杂度：
   遍历原链表一次，时间复杂度为 $O(n)$。

2. 空间复杂度：
   额外分配了两个链表（small 和 big），每个节点仅分配一次，空间复杂度为 $O(n)$。

---

测试用例

以下是测试用例及其输出结果：

输入链表

1 -> 4 -> 3 -> 2 -> 5 -> 2

分区值

x = 3

输出链表

1 -> 2 -> 2 -> 4 -> 3 -> 5

原文地址：https://blog.csdn.net/weixin_48941116/article/details/144206207

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！