前言

本系列主要讲解链表的经典题

注：划重点！！必考~

链表分割

牛客链接：链表分割_牛客题霸_牛客网 (nowcoder.COM)

• 题目描述：

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

• 解题思路：

1. 因为需要相对顺序不变，所以我们选择用尾插法
2. 要将小的放在前面，打的放在后面，这里我们可以选择使用两个链表
3. 一个链接小的结点，另一个链接大的结点，最后再将大的链表尾插到小的链表上

• 参考代码：

/*
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;
    }
};

• 结果：