给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

示例 1：

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

思路一：创建新链表进行修改

struct ListNode* partition(struct ListNode* head, int x){struct ListNode*p1Head=(struct ListNode *)malloc(sizeof(struct ListNode));struct ListNode*p2Head=(struct ListNode *)malloc(sizeof(struct ListNode));struct ListNode*p1=p1Head;struct ListNode*p2=p2Head;struct ListNode*p=head;while(p){if(p->val<x){p1->next=p;p1=p;}else{p2->next=p;p2=p;}p=p->next;}p2->next=NULL;p1->next=p2Head->next;return p1Head->next;}

分析：

本题将小于x的节点全部放在前面，可新建两个个链表，一个存储小于x的节点，一个储存大于等于x的节点，然后连接两个链表再返回新链表

思路二：原地修改

struct ListNode* partition(struct ListNode* head, int x){struct ListNode dummy;dummy.next = head;struct ListNode* slow = &dummy;while(slow->next != NULL && slow->next->val<x){slow = slow->next;}struct ListNode* fast = slow;while(fast && fast->next){if(fast->next->val < x){struct ListNode* tmp = fast->next;fast->next = tmp->next;tmp->next = slow->next;slow->next = tmp;slow = slow->next;}elsefast = fast->next;}return dummy.next;
}

分析：

本题还可使用双指针原地修改链表，将小于x 的节点移动到链表前部。创建一个虚拟头节点 dummy，并将其指向原链表的头部，遍历链表找到第一个大于等于 x 的节点，将慢指针 slow 移动到该节点的前一个位置，通过快指针向后遍历将小于x的节点放置在慢指针后，最后输出

总结：

本题有两种解题思路，创建新链表来存放小于x和大于x的数或利用双指针直接修改原链表，考察了链表相关操作，利用好指针或新建链表即可解决