题目：
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
思路：
代码：
/*** 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 small = new ListNode(0);ListNode smallHead = small;ListNode big = new ListNode(0);ListNode bigHead = big;while (head != null) {if (head.val < x) {small.next = head;small = small.next;} else {big.next = head;big = big.next;}head = head.next;}big.next = null;small.next = bigHead.next;return smallHead.next; }
}性能：
时间复杂度o（n）
空间复杂度o（1）
