题目

面试题 02.04. 分割链表

提示

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你不需要 保留 每个分区中各节点的初始相对位置。

示例 1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：

输入：head = [2,1], x = 2
输出：[1,2]

提示：

• 链表中节点的数目在范围 [0, 200] 内
• -100 <= Node.val <= 100
• -200 <= x <= 200

图解

 

代码(解析在代码注释中)

/*** 定义单链表结构体* struct ListNode {*     int val;         // 节点值*     struct ListNode *next; // 指向下一个节点的指针* };*/typedef struct ListNode ListNode;/*** @brief 将给定的单链表按照指定数值 `x` 进行分区操作，具体思路如下：* - 创建两个链表，分别用于存储小于 `x` 的节点（小链表）和大于等于 `x` 的节点（大链表）* - 遍历原链表，将每个节点与 `x` 进行比较，然后采用尾插法将节点分别插入到小链表或大链表中* - 当遍历结束后，将小链表尾部与大链表头部进行连接，并确保大链表的最后一个节点的 `next` 指针设置为 `NULL`** @param head 输入单链表的头节点指针* @param x 作为分区依据的数值* @return 新的已分区后单链表的头节点指针*/
struct ListNode* partition(struct ListNode* head, int x) {// 初始判断：如果链表为空，则直接返回空指针if (head == NULL) {return head;}// 创建两个链表，分别用于存储小于x的节点和大于等于x的节点，并初始化它们的头尾指针ListNode *Big_head = (ListNode*)malloc(sizeof(ListNode)), *Big_tail = Big_head;ListNode *Small_head = (ListNode*)malloc(sizeof(ListNode)), *Small_tail = Small_head;// 设置两个链表的起始哨兵节点，它们的next指针均初始化为NULLBig_head->next = NULL;Small_head->next = NULL;// 遍历原始链表，根据节点值大小将其插入相应的小链表或大链表中（尾插法）ListNode* tmp = head;while (tmp != NULL) {if (tmp->val < x) {Small_tail->next = tmp;Small_tail = Small_tail->next;} else {Big_tail->next = tmp;Big_tail = Big_tail->next;}tmp = tmp->next; // 移动到下一个待处理的节点}// 确保大链表尾部的next指针置为NULL，以正确结束链表Big_tail->next = NULL;// 将小链表尾部与大链表头部连接起来，形成最终分区后的链表Small_tail->next = Big_head->next;// 释放哨兵节点占用的内存，并重新定位新的链表头指针ListNode* new_head = Small_head->next;free(Small_head);free(Big_head);Small_head = Big_head = NULL;return new_head;
}