题解 | #链表分割#

1.首先审题,可知,需要返回除了小于x的值,其余需要按照顺序返回

2.我们创建两个哨兵位,建立两个新链表,一个存储小于x的值,一个用来存储大于x的值

3.将两个链表连接起来,返回新链表的头节点,(这里需要注意成环问题)

欢迎大家去我的博客留言,我也会分享我做题的心得

https://blog.csdn.net/m0_63111921/article/details/122463378spm=1001.2014.3001.5501

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) 
    {
        struct ListNode*smallhead,*smalltail,*bighead,*bigtail;
        smallhead=smalltail=(struct ListNode*)malloc(sizeof(struct ListNode));
        bighead=bigtail=(struct ListNode*)malloc(sizeof(struct ListNode));
        smalltail->next=NULL;
        bigtail->next=NULL;
        struct ListNode*cur=pHead;
        while(cur)
        {
            if(cur->val<x)
            {
                smalltail->next=cur;
                smalltail=smalltail->next;
            }
            else
            {
                bigtail->next=cur;
                bigtail=bigtail->next;
            }
            cur=cur->next;//迭代
        }
        smalltail->next=bighead->next;
        bigtail->next=NULL;    //这块解决成环问题
        pHead=smallhead->next;
        free(bighead);
        free(smallhead);
        return pHead;
    }
};