分隔链表（ LeetCode 86 ）

算法训练营课程 3年前 0 3.1K 专属

一、题目描述

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

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

二、题目解析

通过构建两个链表来分别处理大于等于 x 的那些节点和小于 x 的那些节点。

大链表：大链表中的所有节点值都是大于或者等于特定值（除了虚拟头节点的值）
小链表：小链表中的所有节点值都是小于特定值（除了虚拟头节点的值）

在遍历原链表的过程中，让大链表去接收那些大于等于 x 的节点，用小链表去接收那些小于 x 的节点，接着让小链表的尾部接上大链表的虚拟头节点的下一个节点，然后让大链表的尾部节点的 next 指针指向 null，最后返回小链表的虚拟头节点的下一个节点就行。

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// https://leetcode-cn.com/problems/partition-list-lcci
class Solution {
    public ListNode partition(ListNode head, int x) {


        // 构建两个新链表
        // 大链表：大链表中的所有节点值都是大于或者等于特定值（除了虚拟头节点的值）
        // 小链表：小链表中的所有节点值都是小于特定值（除了虚拟头节点的值）

        // 设置一个指针，执行大链表的头结点
        ListNode bigHead = new ListNode(-1);

        // 设置一个指针，执行大链表的尾结点
        ListNode bigTail = bigHead;

        // 设置一个指针，执行小链表的头结点
        ListNode smallHead = new ListNode(-1);

        // 设置一个指针，执行小链表的尾结点
        ListNode smallTail = smallHead;

        // 开始遍历原链表 head，直到遍历到尾部位置
        // 在遍历的过程查看当前节点的值
        while ( head != null) {

            // 如果当前节点的值小于了特定值 x
            if (head.val < x) {
                // 那么我们就把这个节点添加到小链表中
                // 操作就是让小链表中的尾节点的 next 指针指向这个节点
                smallTail.next = head;

                // 同时，小链表中的尾节点位置发生了变化，也移动到 head 这个位置
                smallTail = head;
            } else {
                 // 否则，如果当前节点的值大于或者等于了特定值 x
                 // 那么我们就把这个节点添加到大链表中
                 // 操作就是让大链表中的尾节点的 next 指针指向这个节点                 
                 bigTail.next = head;

                 // 同时，大链表中的尾节点位置发生了变化，也移动到 head 这个位置
                 bigTail = head;
            }

            // 操作完当前节点的值之后，继续去查看链表中的下一个节点
            head = head.next;
        }

        // 通过上面的循环，原链表已经被分割为两个部分
        // 其中，大链表中的所有节点值都是大于或者等于特定值（除了虚拟头节点的值）
        // 小链表中的所有节点值都是小于特定值（除了虚拟头节点的值）
        // 接下来，我们把大小链表串联起来

        // 让小链表的尾节点的 next 指针指向大链表虚拟头节点的下一个节点
        smallTail.next = bigHead.next;

        // 让大链表的尾节点的 next 指针指向 null
        bigTail.next = null;

        // 最后返回小链表的虚拟头节点的下一个节点就行
        return smallHead.next;
    }

}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// https://leetcode-cn.com/problems/partition-list-lcci
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {

        // 构建两个新链表
        // 大链表：大链表中的所有节点值都是大于或者等于特定值（除了虚拟头节点的值）
        // 小链表：小链表中的所有节点值都是小于特定值（除了虚拟头节点的值）

        // 设置一个指针，执行大链表的头结点
        ListNode *bigHead = new ListNode(-1);

        // 设置一个指针，执行大链表的尾结点
        ListNode *bigTail = bigHead;

        // 设置一个指针，执行小链表的头结点
        ListNode *smallHead = new ListNode(-1);

        // 设置一个指针，执行小链表的尾结点
        ListNode *smallTail = smallHead;

        // 开始遍历原链表 head，直到遍历到尾部位置
        // 在遍历的过程查看当前节点的值
        while ( head != NULL) {

            // 如果当前节点的值小于了特定值 x
            if (head->val < x) {
                // 那么我们就把这个节点添加到小链表中
                // 操作就是让小链表中的尾节点的 next 指针指向这个节点
                smallTail->next = head;

                // 同时，小链表中的尾节点位置发生了变化，也移动到 head 这个位置
                smallTail = head;
            } else {
                 // 否则，如果当前节点的值大于或者等于了特定值 x
                 // 那么我们就把这个节点添加到大链表中
                 // 操作就是让大链表中的尾节点的 next 指针指向这个节点                 
                 bigTail->next = head;

                 // 同时，大链表中的尾节点位置发生了变化，也移动到 head 这个位置
                 bigTail = head;
            }

            // 操作完当前节点的值之后，继续去查看链表中的下一个节点
            head = head->next;
        }

        // 通过上面的循环，原链表已经被分割为两个部分
        // 其中，大链表中的所有节点值都是大于或者等于特定值（除了虚拟头节点的值）
        // 小链表中的所有节点值都是小于特定值（除了虚拟头节点的值）
        // 接下来，我们把大小链表串联起来

        // 让小链表的尾节点的 next 指针指向大链表虚拟头节点的下一个节点
        smallTail->next = bigHead->next;

        // 让大链表的尾节点的 next 指针指向 null
        bigTail->next = NULL;

        // 最后返回小链表的虚拟头节点的下一个节点就行
        return smallHead->next;
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# https://leetcode-cn.com/problems/partition-list-lcci
class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        # 构建两个新链表
        # 大链表：大链表中的所有节点值都是大于或者等于特定值（除了虚拟头节点的值）
        # 小链表：小链表中的所有节点值都是小于特定值（除了虚拟头节点的值）

        # 设置一个指针，执行大链表的头结点
        bigHead =  ListNode(-1)

        # 设置一个指针，执行大链表的尾结点
        bigTail = bigHead

        # 设置一个指针，执行小链表的头结点
        smallHead =  ListNode(-1)

        # 设置一个指针，执行小链表的尾结点
        smallTail = smallHead

        # 开始遍历原链表 head，直到遍历到尾部位置
        # 在遍历的过程查看当前节点的值
        while head != None :

            # 如果当前节点的值小于了特定值 x
            if head.val < x :
                # 那么我们就把这个节点添加到小链表中
                # 操作就是让小链表中的尾节点的 next 指针指向这个节点
                smallTail.next = head

                # 同时，小链表中的尾节点位置发生了变化，也移动到 head 这个位置
                smallTail = head
            else :
                 # 否则，如果当前节点的值大于或者等于了特定值 x
                 # 那么我们就把这个节点添加到大链表中
                 # 操作就是让大链表中的尾节点的 next 指针指向这个节点                 
                 bigTail.next = head

                 # 同时，大链表中的尾节点位置发生了变化，也移动到 head 这个位置
                 bigTail = head


            # 操作完当前节点的值之后，继续去查看链表中的下一个节点
            head = head.next


        # 通过上面的循环，原链表已经被分割为两个部分
        # 其中，大链表中的所有节点值都是大于或者等于特定值（除了虚拟头节点的值）
        # 小链表中的所有节点值都是小于特定值（除了虚拟头节点的值）
        # 接下来，我们把大小链表串联起来

        # 让小链表的尾节点的 next 指针指向大链表虚拟头节点的下一个节点
        smallTail.next = bigHead.next

        # 让大链表的尾节点的 next 指针指向 None
        bigTail.next = None

        # 最后返回小链表的虚拟头节点的下一个节点就行
        return smallHead.next