单链表OJ题：LeetCode--面试题：02.04 分割链表

2023-06-19 451

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： LeetCode--面试题02.04：分割链表与牛客网--CM11.分割链表联合解题过程，附带完整代码与图解。

朋友们、伙计们，我们又见面了，今天给大家带来的是LeetCode面试题：02.04.分割链表

数据结构：数据结构专栏

作者：stackY、

LeetCode ：LeetCode刷题训练营

LeetCode面试题：02.04.分割链表https://leetcode.cn/problems/partition-list-lcci/

牛客网：CM11 分割链表https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

1.题目介绍

LeetCode：

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

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

编辑

牛客网：

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

编辑

两个题目描述都差不多，但是牛客网要求不能改变相对位置，LeetCode则不在乎相对位置，那么我们就不改变相对位置了。

2.实例演示

编辑

3.解题思路

链表的分割有两种方法：

1.不带哨兵位的头结点

2.带哨兵位的头结点

（两种方法都比较简单，但是带哨兵位的话会稍微的方便一点，这里考虑到有的老铁不知道哨兵位，因此我们两种方法都来演示一下）

3.1不带哨兵位的头结点

不带哨兵位就是直接尾插法：创建两个新的链表，遍历原链表，将小于x的结点尾插到第一个链表head1中，将大于等于x的结点尾插到head2中，尾插结束后将tail2指向的next置为NULL，与原链表断开，然后将head2链接在head1的后面，这里要考虑特殊情况：

1.两个链表第一次尾插时需要注意空指针的问题。

2.在遍历完原链表之后，如果head1为空时可以直接返回head2，如果head2为空，可以直接返回head1。

3.好多老铁好奇为什么不把tail1的next也置为空，这里可以置为空也可以不置为空，因为在下面链接的时候会改变tail1的next。

编辑

LeetCode - 代码演示（C语言实现）：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* partition(struct ListNode* head, int x){
    //创建两个新的链表
    struct ListNode* head1 = NULL;
    struct ListNode* tail1 = NULL;
    struct ListNode* head2 = NULL;
    struct ListNode* tail2 = NULL;
    struct ListNode* cur = head;
    //遍历
    while(cur)
    {
        //小于x的插入第一个链表
        if(cur->val < x)
        {
            //第一次尾插
            if(tail1 == NULL)
            {
                head1 = tail1 = cur;
            }
            else
            {
                tail1->next = cur;
                tail1 = tail1->next;
            }
        }
        //大于或等于x的插入第二个链表
        else
        {
            if(tail2 == NULL)
            {
                head2 = tail2 = cur;
            }
            else
            {
                tail2->next = cur;
                tail2 = tail2->next;
            }
        }
        //迭代
        cur = cur->next;
    }
    //断开与原链表的联系
    if(tail2 != NULL)
    {
        tail2->next = NULL;
    }
    //判断特殊情况
    if(head1 == NULL)
    {
        return head2;
    }
    if(head2 == NULL)
    {
        return head1;
    }
    //链接第一个链表和第二个链表
    tail1->next = head2;
    return head1;
}

牛客网 - 代码实现（C++实现）：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        //创建两个新的链表
    ListNode* head1 = NULL;
    ListNode* tail1 = NULL;
    ListNode* head2 = NULL;
    ListNode* tail2 = NULL;
    ListNode* cur = pHead;
    //遍历
    while(cur)
    {
        //小于x的插入第一个链表
        if(cur->val < x)
        {
            //第一次尾插
            if(tail1 == NULL)
            {
                head1 = tail1 = cur;
            }
            else
            {
                tail1->next = cur;
                tail1 = tail1->next;
            }
        }
        //大于或等于x的插入第二个链表
        else
        {
            if(tail2 == NULL)
            {
                head2 = tail2 = cur;
            }
            else
            {
                tail2->next = cur;
                tail2 = tail2->next;
            }
        }
        //迭代
        cur = cur->next;
    }
    //断开与原链表的联系
    if(tail2 != NULL)
    {
        tail2->next = NULL;
    }
    //判断特殊情况
    if(head1 == NULL)
    {
        return head2;
    }
    if(head2 == NULL)
    {
        return head1;
    }
    //链接第一个链表和第二个链表
    tail1->next = head2;
    return head1;
    }
};

3.2带哨兵位的头结点

带哨兵位的头结点相比较于不带哨兵位的头结点的方法就略显简便，不需要考虑太多的NULL指针的问题，我们依旧采用的是直接尾插法：创建两个新的链表，遍历原链表，将小于x的结点尾插到第一个链表head1中，将大于等于x的结点尾插到head2中，尾插结束后将head2指向的next置为NULL，与原链表断开，然后将head2链接在head1的后面，这里就不需要考虑空指针的问题，直接尾插，尾插结束之后，不能直接将head2链接在tail1的后面，需要将head2的next链接，注意：哨兵位的头节点是动态开辟的，所以要释放掉，因此还要将链接之后的链表再链接在原链表的头上面，释放掉两个有哨兵位的链表：

编辑

LeetCode - 代码演示（C语言实现）：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* partition(struct ListNode* head, int x){
    struct ListNode* head1, *tail1, *head2, *tail2;
    //创建带哨兵位的头结点
    head1 = tail1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    head2 = tail2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* cur = head;
    while(cur)
    {
        //小的链接在第一个链表
        if(cur->val < x)
        {
            tail1->next = cur;
            tail1 = tail1->next;
        }
        else
        {
            tail2->next = cur;
            tail2 = tail2->next;
        }
        //迭代
        cur = cur->next;
    }
    //断开与原链表的联系
    tail2->next = NULL;
    //链接两个新的链表
    tail1->next = head2->next;
    //将新链表链接在原来的头结点上面
    head = head1->next;
    //释放
    free(head1);
    free(head2);
    return head;
}

牛客网 - 代码实现（C++实现）：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        ListNode* head1, *tail1, *head2, *tail2;
    //创建带哨兵位的头结点
    head1 = tail1 = (ListNode*)malloc(sizeof(ListNode));
    head2 = tail2 = (ListNode*)malloc(sizeof(ListNode));
    struct ListNode* cur = pHead;
    while(cur)
    {
        //小的链接在第一个链表
        if(cur->val < x)
        {
            tail1->next = cur;
            tail1 = tail1->next;
        }
        else
        {
            tail2->next = cur;
            tail2 = tail2->next;
        }
        //迭代
        cur = cur->next;
    }
        //断开与原链表的联系
        tail2->next = NULL;
        //链接两个新的链表
        tail1->next = head2->next;
        //将新链表链接在原来的头结点上面
        pHead = head1->next;
        //释放
        free(head1);
        free(head2);
        return pHead;
    }
};