題目：86. 分隔鏈表
思路：雙指針，時間復雜度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
}
)
)
