Leetcode:86分隔链表

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

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

示例:

输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

解题思路：

创建两个链表head1,head2，遍历head中的所有数值，小于x的结点插入head1的表尾，大于或等于x的结点插入head2的表尾。

最后，将head1的表尾连接到head2的表头即可，最终输出head1的表头。

Leetcode:86分隔链表

C++代码
class Solution { public: ListNode* partition(ListNode* head, int x) { ListNode* head1, head2, p, q, pos = head; head1 = new ListNode(0); head2 = new ListNode(0); p = head1; q = head2; while (pos) { if (pos->val < x) { p->next = pos; p = p->next; } else { q->next = pos; q = q->next; } pos = pos->next; } p->next = head2->next; q->next = NULL; return head1->next; } };