题解 | #链表分割#

用C语言写C++的题，前朝的剑斩本朝的官，貌似也不是不行。 思路是很简单的，刨开第一个数字（因为我之前有个想法实现过程中，额外加了头结点结果提示内存占用太大了，后边也就不申请了），判断开头除第一个以外的数字与x的大小，控制着两个指针找到除可能的第一个外其他的大于x的数字，停下来，开始进行第二阶段。 所谓的第二阶段就是一直将p2及指向其前一个单位的p2_f向后移动，找到满足条件的便将它插到p1后边（p1现在一直指着小于x的数字与其他数字的交界线上），然后将p1指向它，保持p1一直在‘边界’，当遍历完所有元素后进入第三阶段。 判断我们之前放过的头结点与x的大小与否，如果它不小于x,那么将它插入到p1后边，而它原本所指的结点成为新的头结点。

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
    	//p1算是个边界标志识位，永远标识着交界处
        ListNode* p1 = pHead;
        //绕开第一个结点开始判断
        ListNode* p2 = pHead->next;
        //判断除头结点后连续的单位是否满足条件，满足则将两个标识向后移动
        while (p2 != NULL && p2->val < x) {
            p1 = p1->next;
            p2 = p2->next;
        }
        //此时的p1与p2仍是紧连的两个元素
        //p2_f标识着p2前一个元素，方便后续操作
        ListNode* p2_f = p1;
        //是否遍历完了整个链表
        while (NULL != p2) {
        	//满足条件则将该元素插到p1后方
            if (p2->val < x) {
                ListNode* tmp = p2;
                p2 = p2->next;
                p2_f->next = p2;
                tmp->next = p1->next;
                p1->next = tmp;
                //保证p1永远在‘边界’
                p1 = tmp;
            }
            //使用p2查看下一个元素
            else {
                p2_f = p2;
                p2 = p2->next;
            }
        }
        //判断第一个元素情况，
        //根据p1位置判断是否进行过元素搬移
        //如果p1都尚未动过，即链表元素均不小于x，还管它第一个元素干甚
        if (pHead->val >= x && p1 != pHead) {
            p2 = pHead->next;
            pHead->next = p1->next;
            p1->next = pHead;
            pHead = p2;
        }
        return pHead;
    }
};