【链表OJ题 5】牛客 CM11 链表分割

落日映苍穹つ 2023-09-27 19:30 10阅读 0赞

**目录**

题目来源：

代码实现：

1.带哨兵位的头结点

2.不带哨兵位的头结点

思路分析：

1.带哨兵位的头结点

实现过程：

易错点：

2.不带哨兵位的头结点

实现过程：

易错点：

--------------------

## 题目来源： ##

[链表分割\_牛客题霸\_牛客网 (nowcoder.com)][_nowcoder.com]

**题目描述：**

![1e77dcc3aeaea27526454e65f4fa624a.png][]

## 代码实现： ##

### 1.带哨兵位的头结点 ###

class Partition {
    public:
        ListNode* partition(ListNode* pHead, int x) {
            // write code here
            struct ListNode* lesshead = NULL, * lesstail = NULL, * greaterhead = NULL,
                * greatertail = NULL, * cur = pHead;
            lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
            greaterhead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode));
    
            while (cur)
            {
                //尾插
                if (cur->val < x)
                {
                    lesstail->next = cur;
                    lesstail = lesstail->next;
                }
                else
                {
                    greatertail->next = cur;
                    greatertail = greatertail->next;
                }
                //迭代
                cur = cur->next;
            }
    
            //连接
            lesstail->next = greaterhead->next;
            //置空大头尾结点的next
            greatertail->next = NULL;
            //将新的头结点指针赋给原头结点指针
            pHead = lesshead->next;
            //释放大小头结点并置空
            free(lesshead);
            lesshead = NULL;
            free(greaterhead);
            greaterhead = NULL;
    
            return pHead;
        }
    };

### 2.不带哨兵位的头结点 ###

class Partition {
    public:
        ListNode* partition(ListNode* pHead, int x) {
            // write code here
            struct ListNode* lesshead = NULL, * lesstail = NULL, * greaterhead = NULL,
                * greatertail = NULL;
    
            while (pHead)
            {
                //尾插
                if (pHead->val < x)
                {
                    if(NULL == lesstail)
                    {
                        lesshead = lesstail = pHead;
                    }                    
                    else
                    {
                        lesstail->next = pHead;
                        lesstail = lesstail->next; 
                    }
                }
                else
                {
                    if(NULL == greatertail)
                    {
                        greaterhead = greatertail = pHead;
                    }                    
                    else
                    {
                        greatertail->next = pHead;
                        greatertail = greatertail->next; 
                    }
                }
                //迭代
                pHead = pHead->next;
            }
    
            //小头为空
            if(lesshead != NULL && greaterhead == NULL)
            {
                lesstail = NULL;
                return lesshead;
            }
            //大头为空
            if(lesshead == NULL && greaterhead != NULL)
            {
                greatertail = NULL;
                return greaterhead;
            }
            //连接
            lesstail->next = greaterhead;
            //置空大头尾结点的next
            greatertail->next = NULL;
    
            return lesshead;
        }
    };

## 思路分析： ##

## 1.带哨兵位的头结点 ##

![4db68b35e6b27ebea70cae0c04e5a992.png][]

为实现本题，我们先将原链表头结点赋给cur，再开辟两个结构体，并将其分别赋给结构体指针变量，lesshead = lesstail，greaterhead = greatertail。小于 x 尾插在 lesstail->next 上，大于 x 尾插在 greatertail->next 上。

### 实现过程： ###

1.创建两个带哨兵位的新链表，分别存放小于 x 的所有结点和大于 x 的所有结点。我们定义小于 x 的头尾结点为lesshead，lesstail；定义大于 x 的头尾结点为 greaterhead，greatertail。

2.遍历链表，val < x 那么就尾插在 lesstail->next，val > x 那么就尾插在 greatertail->next。然后更新原链表的头结点和插入后的尾指针，分别都往后走一步。

3.循环步骤2，遍历完整个原链表，这时也就将大小分开了，再将 lesstail->next = greaterhead->next 并将greatertail->next = NULL，再将新的头结点赋值给原链表头，pHead = lesshead->next（因为最后要释放掉lesshead与greaterhead，并置空，所以要将小头结点赋值给pHead）。

4.释放 lesshead，greaterhead，并返回 pHead。

#### 易错点： ####

**可能会出现环形链表：**

![15b05ea7045179e8fa8a4f97014ad4d3.png][]

**为了避免这种情况的发生，我们最后将 greatertail->next = NULL 处理，这样就避免了这种情况。**

![4c4201cdabea2f83465e7d8c1d437cda.png][]

![45285494149834104988da2dfd58e12c.png][]

![013f3b38bed7a87d2452d356d9e4522a.png][]

## 2.不带哨兵位的头结点 ##

主要的思路是一致的，只是这次我们不开辟结构体，直接定义结构体指针lesshead、lesstail，greaterhead、greatertail，并将其置空。

![374ec89bf9d88ca2533f4514ca3c2453.png][]

### 实现过程： ###

与带哨兵位的头结点实现过程类似，**不同点：**

1.连接那块，lesstail->next = greaterhead，因为这次没有哨兵位，不用连接next。

2.返回值lesshead不是动态开辟的，不用释放，因此就不用再赋回去，直接返回 lesshead。

#### 易错点： ####

**1> 可能会出现环形链表：**

![5ca3b298ed2badfbf65f968975e7fc33.png][]

**为了避免这种情况的发生，我们最后将 greatertail->next = NULL 处理，这样就避免了这种情况。**

![fd7e4eb8149505a7d3dd56de87c63fdb.png][]

**2> 将大小分开后 lesshead或者greaterhead 可能为空，需要判断：**

//小头为空
    if(lesshead != NULL && greaterhead == NULL)
    {
        lesstail = NULL;
        return lesshead;
    }
    //大头为空
    if(lesshead == NULL && greaterhead != NULL)
    {
        greatertail = NULL;
        return greaterhead;
    }

![d54efa1a126fa16dd8b3126122ecba3f.png][]

![b14d0396c22b498ef5a5d96b40c67870.png][]

如果大牛的您看到有什么问题留言给我，我一定会认真看的，谢谢您。如果您看了觉得有收获，关注 + 点赞支持一下呗。

\*\*\* 本篇结束 \*\*\*

[_nowcoder.com]: https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
[1e77dcc3aeaea27526454e65f4fa624a.png]: https://img-blog.csdnimg.cn/img_convert/1e77dcc3aeaea27526454e65f4fa624a.png
[4db68b35e6b27ebea70cae0c04e5a992.png]: https://img-blog.csdnimg.cn/img_convert/4db68b35e6b27ebea70cae0c04e5a992.png
[15b05ea7045179e8fa8a4f97014ad4d3.png]: https://img-blog.csdnimg.cn/img_convert/15b05ea7045179e8fa8a4f97014ad4d3.png
[4c4201cdabea2f83465e7d8c1d437cda.png]: https://img-blog.csdnimg.cn/img_convert/4c4201cdabea2f83465e7d8c1d437cda.png
[45285494149834104988da2dfd58e12c.png]: https://img-blog.csdnimg.cn/img_convert/45285494149834104988da2dfd58e12c.png
[013f3b38bed7a87d2452d356d9e4522a.png]: https://img-blog.csdnimg.cn/img_convert/013f3b38bed7a87d2452d356d9e4522a.png
[374ec89bf9d88ca2533f4514ca3c2453.png]: https://img-blog.csdnimg.cn/img_convert/374ec89bf9d88ca2533f4514ca3c2453.png
[5ca3b298ed2badfbf65f968975e7fc33.png]: https://img-blog.csdnimg.cn/img_convert/5ca3b298ed2badfbf65f968975e7fc33.png
[fd7e4eb8149505a7d3dd56de87c63fdb.png]: https://img-blog.csdnimg.cn/img_convert/fd7e4eb8149505a7d3dd56de87c63fdb.png
[d54efa1a126fa16dd8b3126122ecba3f.png]: https://img-blog.csdnimg.cn/img_convert/d54efa1a126fa16dd8b3126122ecba3f.png
[b14d0396c22b498ef5a5d96b40c67870.png]: https://img-blog.csdnimg.cn/img_convert/b14d0396c22b498ef5a5d96b40c67870.png