@@ -0,0 +1,2416 @@
+/***%0A * Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.%0A *%0A * You should preserve the original relative order of the nodes in each of the two partitions.%0A *%0A * For example,%0A * Given 1-%3E4-%3E3-%3E2-%3E5-%3E2 and x = 3,%0A * return 1-%3E2-%3E2-%3E4-%3E3-%3E5.%0A */%0A/**%0A * Definition for singly-linked list.%0A * public class ListNode %7B%0A *     int val;%0A *     ListNode next;%0A *     ListNode(int x) %7B%0A *         val = x;%0A *         next = null;%0A *     %7D%0A * %7D%0A */%0Apublic class Solution %7B%0A    // Solution 1: O(n), O(1)%0A    /*%0A    public ListNode partition(ListNode head, int x) %7B%0A        if (head == null %7C%7C head.next == null)%0A            return head;%0A        ListNode head1 = null, head2 = null;%0A        ListNode cur = head;%0A        ListNode cur1 = null, cur2 = null;%0A        while (cur != null) %7B%0A            if (cur.val %3C x) %7B%0A                if (head1 == null) %7B%0A                    head1 = cur;%0A                    cur1 = head1;%0A                    cur = cur.next;%0A                %7D else %7B%0A                    cur1.next = cur;%0A                    cur = cur.next;%0A                    cur1 = cur1.next;%0A                %7D%0A            %7D else %7B%0A                if (head2 == null) %7B%0A                    head2 = cur;%0A                    cur = cur.next;%0A                    cur2 = head2;%0A                %7D else %7B%0A                    cur2.next = cur;%0A                    cur = cur.next;%0A                    cur2 = cur2.next;%0A                %7D%0A            %7D%0A        %7D%0A        if (head1 == null)  return head2;%0A        if (head2 == null)  return head1;%0A        cur1.next = head2;%0A        cur2.next = null;%0A        return head1;%0A    %7D%0A    */%0A%0A    // Solution 2: O(n), O(1)%0A    //%0A    public ListNode partition(ListNode head, int x) %7B%0A        if (head == null %7C%7C head.next == null)%0A            return head;%0A        ListNode head_left = new ListNode(1);%0A        ListNode head_right = new ListNode(1);%0A%0A        ListNode cur_left = head_left;%0A        ListNode cur_right = head_right;%0A%0A        for (ListNode cur = head; cur != null; cur = cur.next) %7B%0A            if (cur.val %3C x) %7B%0A                cur_left.next = cur;%0A                cur_left = cur;%0A            %7D else %7B%0A                cur_right.next = cur;%0A                cur_right = cur;%0A            %7D%0A        %7D%0A        cur_left.next = head_right.next;%0A        cur_right.next = null;%0A%0A        return head_left.next;%0A    %7D%0A%7D%0A

add PartitionList.java