Concise java code with explanation, one pass


  • 88

    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) {
                curr1.next = head;
                curr1 = head;
            }else {
                curr2.next = head;
                curr2 = head;
            }
            head = head.next;
        }
        curr2.next = null;          //important! avoid cycle in linked list. otherwise u will get TLE.
        curr1.next = dummy2.next;
        return dummy1.next;
    }

  • 5
    W

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

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

    so why needing this?


  • 12
    Z

    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
    E

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


  • 1
    C

    Agree, every time when it does curr1.next = 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
    A

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


  • 0
    Y

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


Log in to reply
 

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