Leetcode86. 分隔链表

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

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

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

示例1：

 

/*** 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(-1);ListNode smallHead = small;ListNode large = new ListNode(-1);ListNode largeHead = large;while(head != null){if(head.val < x){small.next = head;small = small.next;}else{large.next = head;large = large.next;}head = head.next;}//防止原链表中的大于等于X的节点在链表中间某个位置，这样large.next = null;small.next = largeHead.next;return smallHead.next;}
}