给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
class Solution { public ListNode partition(ListNode head, int x) { ListNode smallHead = new ListNode(0); ListNode smallCurr = smallHead; ListNode bigHead = new ListNode(0); ListNode bigCurr = bigHead; while(head!=null){ if(head.val < x) { smallCurr.next=head; smallCurr=smallCurr.next; } if(head.val >= x) { bigCurr.next = head; bigCurr=bigCurr.next; } head=head.next; } //遍历结束后,我们将 large 的 next 指针置空,这是因为当前节点复用的是原链表的节点 //,而其 next 指针可能指向一个小于x的节点,我们需要切断这个引用。 bigCurr.next=null; smallCurr.next=bigHead.next; return smallHead.next; } }