国外的设计网站,网站浮窗代码,湖南有实力的关键词优化,为女人网上量体做衣网站题目
面试题 02.04. 分割链表
提示
给你一个链表的头节点 head 和一个特定值 x #xff0c;请你对链表进行分隔#xff0c;使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你不需要 保留 每个分区中各节点的初始相对位置。 示例 1#xff1a; 输入#xff…题目
面试题 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;
}
