02.04、分割链表

02.04、[中等] 分割链表

1、题目描述

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

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

2、解题思路

本题要求将链表分隔，使得所有小于 x 的节点排在大于或等于 x 的节点之前。链表中的节点顺序不需要保持。我们的目标是创建两个链表，一个存储小于 x 的节点，另一个存储大于等于 x 的节点，最后将两个链表拼接起来。

1. 创建两个链表：
   • 一个用于存放小于 x 的节点 (less)。
   • 一个用于存放大于等于 x 的节点 (greater)。
2. 遍历原链表：
   • 对于每个节点，判断其值与 x 的大小：
     • 如果节点值小于 x，将其添加到 less 链表。
     • 如果节点值大于等于 x，将其添加到 greater 链表。
3. 拼接两个链表：
   • 遍历完原链表后，将 less 链表的最后一个节点指向 greater 链表的头节点。
   • greater 链表的最后一个节点需要指向 null，表示链表的结束。
4. 返回结果：
   • 返回 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、关键点总结

1. 虚拟节点：
   • 使用 ListNode() 创建虚拟头节点，避免处理头节点的特殊情况，简化代码逻辑。
2. 链表拼接：
   • 遍历原链表的过程中，将节点分别加入到 less 或 greater 链表。遍历完后，将 less 链表与 greater 链表拼接在一起。
3. 尾节点处理：
   • 注意在拼接链表后，greater 链表的最后一个节点需要指向 nullptr，防止链表成环。

5、时间复杂度与空间复杂度

• 时间复杂度： O(n)，其中 n 是链表的长度。我们只遍历了链表一次。
• 空间复杂度： O(1)，因为我们只是创建了两个辅助链表指针，额外空间与输入大小无关。

原文地址：https://blog.csdn.net/mmlhbjk/article/details/142035759

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