Concise java code with explanation, one pass

  • 89

    the basic idea is to maintain two queues, the first one stores all nodes with val less than x , and the second queue stores all the rest nodes. Then concat these two queues. Remember to set the tail of second queue a null next, or u will get TLE.

    public ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode(0), dummy2 = new ListNode(0);  //dummy heads of the 1st and 2nd queues
        ListNode curr1 = dummy1, curr2 = dummy2;      //current tails of the two queues;
        while (head!=null){
            if (head.val<x) {
       = head;
                curr1 = head;
            }else {
       = head;
                curr2 = head;
            head =;
        } = null;          //important! avoid cycle in linked list. otherwise u will get TLE. =;

  • 5

    sorry, still not getting why need this? = null;

    cur2 is already pointing to the last node of the origin list, which means =null should always guarantee.

    so why needing this?

  • 12

    For this list: 5->6->1->2, x=3, at last cur2 points to 6, cur1 points to 2, we must set 6->1 to 6->null, otherwise there will be a cycle.

  • 0

    Very brilliant, thanks very much for pointing out this case.

  • 1

    Agree, every time when it does = head;, it actually put the whole remaining list to the tail of curr1, and in the next loop it sets .next to be the next remaining list.. Luckily it doesn't cause trouble in the question, as it doesn't involve any mutation in the original list. I prefer creating new instance with value, and that way you don't need to set null for the tail.

  • 0

    What if all the node values are larger or equal to x? Then will be null. In this case, it is better to see if == null, if this is true, then you can directly return

  • 0

    @adrrrrrrrian no need to check if == null, 'cause if all nodes's values are greater or equal to x, curr1 will always equals dummy1. This line = will result in dummy1 directly pointing to;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.