package com.q0086;

import com.q0086_partition_list.ListNode;

/**

* https://leetcode-cn.com/problems/partition-list/

* 86. 分隔链表

*/

public class Solution {

public ListNode partition(ListNode head, int x) {

ListNode dummyHead1 = new ListNode(0);

ListNode dummyHead2 = new ListNode(0);

ListNode prev1 = dummyHead1;

ListNode prev2 = dummyHead2;

//x 3

//p1 c

//0-->1-->4-->3-->2-->5-->2

//0-->1-->2-->2-->4-->3-->5

ListNode cur = head;

while (cur != null) {

if (cur.val < x) {

prev1.next = cur;

cur = cur.next;

prev1 = prev1.next;

prev1.next = null;

} else {

prev2.next = cur;

cur = cur.next;

prev2 = prev2.next;

prev2.next = null;

}

}

prev1.next = dummyHead2.next;

return dummyHead1.next;

}

}