《手撕链表题系列-6》链表分割

/*
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*longhead=(struct ListNode*)malloc(sizeof(struct ListNode));
        longhead->next=NULL;
    struct ListNode*lesshead=(struct ListNode*)malloc(sizeof(struct ListNode));
        lesshead->next=NULL;
        //创建寻址指针
        struct ListNode*cur1=pHead,*cur2=longhead,*cur3=lesshead;
        while(cur1)
        {
            //根据节点数据大小决定接上的链表的位置
            if(cur1->val<x)
            {
                cur3->next=cur1;
                cur3=cur1;
            }
            else
            {
                cur2->next=cur1;
                cur2=cur1;
            }
            //找下一个节点
            cur1=cur1->next;
        }
        //尾节点置空，避免成环
        cur2->next=NULL;
        //两个链表接成一条
        cur3->next=longhead->next;
        //记录头结点位置
        struct ListNode*next=lesshead->next;
        //释放哨兵卫
        free(longhead);
        free(lesshead);
        return next;
    }
};