[数据结构与算法]LeetCode 86题

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。你应当 保留 两个分区中每个节点的初始相对位置。

示例 1：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/partition-list

思想：创建两个新链表，一个用来存放小于x的值，一个用来存放大于xde 值;每一个新链表开辟两个新节点指针Tail,Head,意味着用来指向表头和表尾;Head在那站桩不动以便后续返回新链表 Tail则不断更新

注意：防止链表循环，例如：原链表为1->4->3->2->5->2->NULL给定值为3

lessHead:1->2->2->NULL

greaterHead:4->3->5->NULL

新链表应为:1->2->2->4->3->5->NULL在这里若5的next域没有置空，则它的next仍指向原链表所指向的2，而在新链表中2的next域又指向4如此就形成了循环，就会导致崩

struct ListNode* partition(struct ListNode* head, int x)
{
struct ListNode*cur;
struct ListNode*lessTail;
struct ListNode*lessHead;
struct ListNode*greaterTail;
struct ListNode*greaterHead;
lessTail=lessHead=(struct ListNode*)malloc(sizeof(struct ListNode));
lessTail->next=NULL;
greaterTail=greaterHead=(struct ListNode*)malloc(sizeof(struct ListNode));
greaterTail->next=NULL;
cur=head;//开创一个哨兵结点
while(cur)
{
    if(cur->val<x)//将原链表小于x的值尾插进lessTail
    {
        lessTail->next=cur;
        lessTail=cur;//尾插值在不断更新
    }
    else
    {
        greaterTail->next=cur;//将大于x的数据尾插在greaterTail后面
        greaterTail=cur;
    }
    cur=cur->next;//在cur不为空的情况下执行完上面判断
    
}
lessTail->next=greaterHead->next;//存放值大于x的整体链表插入到存放值小于x的链表后面
greaterTail->next=NULL;//将新链表表尾置空，不然若新链表表尾元素在原链表不是表尾，新链表表尾它的next就会指向那个值形成循环链表
struct ListNode*pre=lessHead->next;//销毁开辟出来的新节点
free(lessHead);//释放
free(greaterHead);//释放

return pre;//返回新链表
}

由于编者能力有限，在这篇文章中若有不足之处请各位网友在评论区指正。其次由于是第一次写博客些许排版并不熟练，请各位海涵