【算法笔记】LeetCode_86 分隔链表

LeetCode_86 分隔链表

LeetCode_86 分隔链表

题目描述

给你一个链表的头节点 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

思路

这道题算是中等难度里面比较简单的了，但有个小坑困扰了我半个小时，特此记录一下：

题目整体思路很简单，解答的时候可以想象在给苹果分类，比如给你一批苹果，大小不一，然后你面前有两个桶，左边的桶写着（直径大于15cm），右边的桶写着（其他），然后你依次测量苹果直径然后放进两个桶内，至于题目说的“保持原始的次序”，由于链表的特性，这个不是问题。

所以我们初始化两个局部对象ListNode * leftPart， rightPart，然后对原始链表进行遍历，如果当前节点的val小于x就连接到leftPart，否则连接到rightPart，最后，连接leftPart的末尾和rightPart的开头，非常简单。

我说的小坑是：一定不要忘记将新链表的最后一个node指向nullptr，否则整个链表可能产生环，运行不过

代码解析

class Solution {  
public:  
    ListNode* partition(ListNode* head, int x) {  
        // 如果链表为空或只有一个节点，则无需分区，直接返回原链表  
        if (head == nullptr || head->next == nullptr)  
        {  
            return head;  
        }  
        
        // 初始化左、右两个链表的虚拟头节点  
        ListNode * leftPart = new ListNode();  
        ListNode * leftHead = leftPart;  
        ListNode * rightPart = new ListNode();  
        ListNode * rightHead = rightPart;  
        
        // 遍历原链表  
        while(head != nullptr)  
        {  
            // 如果当前节点的值小于x，将其加入左链表  
            if (head->val < x)  
            {  
                leftPart->next = head;  
                leftPart = leftPart->next;  
            }  
            // 如果当前节点的值大于等于x，将其加入右链表  
            else  
            {  
                rightPart->next = head;  
                rightPart = rightPart->next;  
            }  
            // 移动到原链表的下一个节点  
            head = head->next;  
        }  
        
        // 将右链表的末尾置为nullptr，防止成环  
        rightPart->next = nullptr;  
        
        // 将左链表的末尾指向右链表的头节点，形成新的链表  
        leftPart->next = rightHead->next;  
        
        // 返回新链表的头节点（左链表的第二个节点）  
        return leftHead->next;  
    }  
};

思想

这段代码使用了双指针的思想，通过遍历原链表，将节点按照值的大小分别连接到两个新的链表（左链表和右链表）中。最后，将右链表的头节点之前的节点（即虚拟头节点）断开，并将左链表的末尾指向右链表的头节点，从而完成链表的分区。

方法

• 创建两个虚拟头节点leftPart和rightPart来初始化左链表和右链表。
• 遍历原链表，根据节点的值将节点分别加入到左链表或右链表中。
• 遍历结束后，将右链表的末尾置为nullptr，防止成环。
• 将左链表的末尾指向右链表的头节点，形成新的链表。
• 返回新链表的头节点。

时间复杂度

时间复杂度为O(n)，其中n是链表的长度。因为只需要遍历一次链表。

空间复杂度

空间复杂度为O(1)。虽然创建了四个新的ListNode对象，但它们是固定数量的，不随链表长度的变化而变化。因此，空间复杂度是常数级别的。