思路：双指针，时间复杂度0(n)。
双指针来维护小于x的链表和不小于x的链表即可，后面将两个链表连起来即可。

C++版本：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* partition(ListNode* head, int x) {ListNode *p =new ListNode(0);ListNode *q =new ListNode(0);ListNode *p0=p,*q0=q;while(head!=nullptr){if(head->val<x){p->next=head;p=p->next;}else{q->next=head;q=q->next;}head=head->next;}p->next=q0->next;q->next=nullptr;return p0->next;}
};

JAVA版本：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode partition(ListNode head, int x) {ListNode p =new ListNode(0);ListNode q =new ListNode(0);ListNode p0=p,q0=q;while(head!=null){if(head.val<x){p.next=head;p=p.next;}else{q.next=head;q=q.next;}head=head.next;}p.next=q0.next;q.next=null;return p0.next;}
}

GO版本：

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func partition(head *ListNode, x int) *ListNode {p,q:=&ListNode{Val:0},&ListNode{Val:0}p0,q0:=p,qfor head!=nil {if head.Val<x {p.Next=headp=p.Next}else{q.Next=headq=q.Next}head=head.Next}p.Next=q0.Nextq.Next=nilreturn p0.Next
}