【CM11 链表分割】

---

一、题目描述

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

题目链接

---

二、提供方便走读代码的图

---

三、题目代码

提示：注意死循环，一定要把bigTail->next置NULL

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/
class Partition {
    
public:
    ListNode* partition(ListNode* pHead, int x) {
    
        ListNode* smallHead=(ListNode*)malloc(sizeof( ListNode));
        smallHead->next=NULL;
        ListNode* bigHead=(ListNode*)malloc(sizeof( ListNode));
        bigHead->next=NULL;
        ListNode* cur,*bigTail,*smallTail;
        cur=pHead;
        smallTail=smallHead;
        bigTail=bigHead;
        while(cur)
        {
    
            if(cur->val<x)
            {
    
                smallTail->next=cur;
                smallTail=smallTail->next;
            }
            else
            {
    
                bigTail->next=cur;
                bigTail=bigTail->next;
            }
            cur=cur->next;
        }
        bigTail->next=NULL;
        smallTail->next=bigHead->next;
        ListNode* newHead=smallHead->next;
        free(smallHead);
        free(bigHead);
        return newHead;
    
    }
};

---

以上是本篇文章的全部内容，如果文章有错误或者有看不懂的地方，多和喵博主交流。互相学习互相进步。如果这篇文章对你有帮助，可以给喵博主一个关注，你们的支持是我最大的动力。