做网站推广什么好,成都建设银行保安招聘网站,素材公社免费素材网,软件开发文档国标02.04、[中等] 分割链表
1、题目描述
给你一个链表的头节点 head 和一个特定值 x #xff0c;请你对链表进行分隔#xff0c;使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你不需要 保留 每个分区中各节点的初始相对位置。
2、解题思路
本题要求将链表分隔…02.04、[中等] 分割链表
1、题目描述
给你一个链表的头节点 head 和一个特定值 x 请你对链表进行分隔使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你不需要 保留 每个分区中各节点的初始相对位置。
2、解题思路
本题要求将链表分隔使得所有小于 x 的节点排在大于或等于 x 的节点之前。链表中的节点顺序不需要保持。我们的目标是创建两个链表一个存储小于 x 的节点另一个存储大于等于 x 的节点最后将两个链表拼接起来。
创建两个链表 一个用于存放小于 x 的节点 (less)。一个用于存放大于等于 x 的节点 (greater)。 遍历原链表 对于每个节点判断其值与 x 的大小 如果节点值小于 x将其添加到 less 链表。如果节点值大于等于 x将其添加到 greater 链表。 拼接两个链表 遍历完原链表后将 less 链表的最后一个节点指向 greater 链表的头节点。greater 链表的最后一个节点需要指向 null表示链表的结束。 返回结果 返回 less 链表的头节点即跳过辅助节点。
3、代码实现与详细注释
class Solution {
public:ListNode* partition(ListNode* head, int x) {// 创建两个虚拟节点作为新链表的头一个用于小于x的节点另一个用于大于等于x的节点ListNode* less new ListNode(0); // 用于存放小于x的节点ListNode* greater new ListNode(0); // 用于存放大于等于x的节点// 初始化当前遍历的指针以及两个链表的末尾指针ListNode *cur head, *cur1 less, *cur2 greater;// 遍历整个链表while (cur) {if (cur-val x) {// 当前节点值小于x将该节点加入到less链表cur1-next cur;cur1 cur1-next; // 移动less链表末尾指针} else {// 当前节点值大于等于x将该节点加入到greater链表cur2-next cur;cur2 cur2-next; // 移动greater链表末尾指针}// 移动到链表的下一个节点cur cur-next;}// 将less链表与greater链表连接起来cur1-next greater-next;// 将greater链表的最后一个节点指向null避免成环cur2-next nullptr;// 返回less链表的头节点跳过第一个虚拟节点return less-next;}
};4、关键点总结
虚拟节点 使用 ListNode() 创建虚拟头节点避免处理头节点的特殊情况简化代码逻辑。 链表拼接 遍历原链表的过程中将节点分别加入到 less 或 greater 链表。遍历完后将 less 链表与 greater 链表拼接在一起。 尾节点处理 注意在拼接链表后greater 链表的最后一个节点需要指向 nullptr防止链表成环。
5、时间复杂度与空间复杂度
时间复杂度 O(n)其中 n 是链表的长度。我们只遍历了链表一次。空间复杂度 O(1)因为我们只是创建了两个辅助链表指针额外空间与输入大小无关。
