每日一题---OJ题：分隔链表

片头

嗨！小伙伴们，大家好！今天我们一起来看看这道题----分隔链表

emmmm，这道题，看描述应该不算太难，我们一起来画一画图呗！

题目读懂了，那么如何破解这道题呢？

思路：定义2个链表，大链表和小链表，遍历原链表的节点将其放到对应的新链表中，最后将大链表和小链表首尾相连。

第一次：

第二次：

第三次：

第四次：

第五次：

第六次：

OK,现在pcur在原链表中，已经走到NULL的位置，循环结束，部分代码如下：

         typedef struct ListNode ListNode;//如果链表为空，返回空if(head == NULL){return head;}//pcur遍历原链表ListNode* pcur = head;//创建小链表，创建小链表的哨兵节点ListNode* lessHead = NULL;ListNode* lessTail = NULL;lessHead = lessTail =(ListNode*) malloc(sizeof(ListNode));//创建大链表，创建大链表的哨兵节点ListNode* greateHead = NULL;ListNode* greateTail = NULL;greateHead = greateTail =(ListNode*) malloc(sizeof(ListNode));//当pcur遍历到空时，退出循环while(pcur!=NULL){if(pcur->val < x){//尾插到小链表中lessTail->next = pcur;lessTail = pcur;}else{//尾插到大链表中greateTail->next = pcur;greateTail = pcur;}//pcur指向下一个节点pcur = pcur->next;}

接下来，我们需要让greateTail的next指针指向NULL，如果不置为NULL的话，就会形成一个环，

下一步，怎么让小链表和大链表连接起来呢？很简单，让 lessTail->next = greateHead->next 就可以啦！

最后一步，就是用一个节点来保存第一个节点，把2个哨兵节点释放,返回第一个有效节点就可以啦！

ListNode* ret = lessHead->next;
free(lessHead);
free(greateHead);
return ret;

OK，这道题被我们解决了，完整代码如下：

 typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x) {//如果链表为空，返回空if(head == NULL){return head;}//pcur遍历原链表ListNode* pcur = head;//创建小链表，创建小链表的哨兵节点ListNode* lessHead = NULL;ListNode* lessTail = NULL;lessHead = lessTail =(ListNode*) malloc(sizeof(ListNode));//创建大链表，创建大链表的哨兵节点ListNode* greateHead = NULL;ListNode* greateTail = NULL;greateHead = greateTail =(ListNode*) malloc(sizeof(ListNode));//当pcur遍历到空时，退出循环while(pcur!=NULL){if(pcur->val < x){//尾插到小链表中lessTail->next = pcur;lessTail = pcur;}else{//尾插到大链表中greateTail->next = pcur;greateTail = pcur;}//pcur指向下一个节点pcur = pcur->next;}//大链表最后一个结点的next指针指向NULLgreateTail->next = NULL;//小链表最后一个节点指向大链表的第一个有效节点lessTail->next = greateHead->next;//用ret来保存小链表的第一个有效节点ListNode* ret = lessHead->next;//将哨兵节点释放free(lessHead);free(greateHead);//将ret返回return ret;
}