题目：

给你一个链表的头节点 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）