@@ -0,0 +1,1354 @@
+// 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%09// simple idea: create left and right sublist, iterate through input list and append each node%0A%09// to list where it should be.%0A%09// space: O(n) time:O(n)%0A    public ListNode partition(ListNode head, int x) %7B%0A    %09if(head == null %7C%7C head.next == null) return head;%0A%0A    %09ListNode leftHead =new ListNode(0);%0A    %09ListNode leftTail = leftHead;%0A    %09ListNode rightHead = new ListNode(0);%0A    %09ListNode rightTail = rightHead;%0A    %09ListNode runner = head;%0A%0A    %09while(runner != null)%7B%0A    %09    ListNode next = runner.next;%0A    %09%09if(runner.val %3C x)%7B%0A    %09%09%09leftTail.next = runner;%0A    %09%09%09leftTail = leftTail.next;%0A    %09%09%7Delse%7B%0A    %09%09%09rightTail.next = runner;%0A    %09%09%09rightTail = rightTail.next;%0A    %09%09%7D%0A            runner.next = null;%0A    %09%09runner = next;%0A    %09%7D%0A%0A    %09leftTail.next = rightHead.next;%0A%0A    %09return leftHead.next;%0A    %7D%0A%7D

add partition list solution