题解 | #链表分割#

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
//在c++中我们不需要重新定义名字，我们直接用ListNode

/*
思路：我么还能创建一个大链表，一个小链表
将遍历原先的链表，将比x小的节点放到小链表里面
将比x大的节点放到大链表里面
然后我们再进行大小链表的对接
3我们将小链表的尾链表的下一个节点变成大链表头结点的下一个节点
因为我们在创建的大小链表的时候，用的是malloc开辟的节点，因此大小链表的头结点就相当一个站位置的
并不是一个有效的节点
*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x)//返回链表的头节点
    {
        //创建两个非空链表
        ListNode*lessHead,*lessTail; 
        //小链表
        lessHead=lessTail=(ListNode*)malloc(sizeof(ListNode));//开辟一个节点大小的空间
        //大链表
        ListNode*greaterHead,*greaterTail;
        greaterHead=greaterTail=(ListNode*)malloc(sizeof(ListNode));

        //创建一个临时指针遍历链表，找小于x的和其他节点位插到大小链表中
        ListNode*pcur=pHead;//初始化指向头节点
        while(pcur)//等价与pcur!=NULL
        {
            if(pcur->val<x)//尾插到小链表
            {
                //因为我们的大小链表都是非空的，那么我们直接往头节点后面进行尾插
                lessTail->next=pcur;
                lessTail=lessTail->next;//尾节点走到新的位置
            }
            else //尾插到大链表
            {
                greaterTail->next=pcur;
                greaterTail=greaterTail->next;
            }
            pcur=pcur->next;//pcur换下个节点进行比较
            
        }
        //跳出循环，说明此时我们的原链表已经遍历完了
        //我们现在要让大链表和小链表进行首尾相连
        lessTail->next=greaterHead->next;
        greaterTail->next=NULL;
        //此时我们要将lessHead和greatHead进行释放
        //但是我们题目要求是将新的链表的头结点进行返回，
        //但是如果我们先将lessHead进行释放的话，那么我们是无法找到头节点的
        //所以我们在释放操作之前我们需要将头结点进行比保存
        //定义一个指针指向小节点第一个有效的节点
        ListNode*ret=lessHead->next;
        free(lessHead);
        lessHead=NULL;
        free(greaterHead);
        greaterHead=NULL;


        //返回头节点
        return ret;
    }
};/*
对于这个题来说的话
假设我们原先的链表是5->1->3->6->2
经过一系列操作后我们得到了大小两个链表
小链表：头结点->1->2
大链表：头节点—>5-3->6

再次进行操作得到了
1->2—>5-3->6  
但是我们有没有想过这个题目会出现死循环呢？
因为在之前我们没有对6的下个节点进行操作，如果不进行操作的话
那么这个链表的指向就是这样的：1->2—>5-3->6->2—>5-3->6->2—>5-3->6 .......
所以我们需要将6的下个节点指向NULL




*/