给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode partition(ListNode head, int x) { ListNode d1 = new ListNode(-1); ListNode d2 = new ListNode(-2); ListNode d11 = d1; ListNode d22 = d2; ListNode cur = head; while(cur != null){ if(cur.val < x){ d1.next = cur; d1 = d1.next; }else{ d2.next = cur; d2 = d2.next; } cur = cur.next; } d1.next = d22.next; //最后一个数不一定为>=x的数 d2.next = null; return d11.next; } }