一、原題

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. You should PReserve the original relative order of the nodes in each of the two partitions. 

一、中文

給定一個單鏈表和一個值x，將鏈表分成小于等于x的部分和大于x的部分。同時保持鏈表原來的相對順序

三、舉例

Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5. 

四、思路

 創建兩個鏈表，編譯單鏈表，將鏈表中比較小的元素放到左邊的鏈表中，比較大的放入到右邊的鏈表中

最后將兩個鏈表進行合并就可以了。

五、程序

package code;public class LeetCode47{	public static void main(String args[]){		ListNode list1 = new ListNode(1);		ListNode list2 = new ListNode(4);		ListNode list3 = new ListNode(2);		ListNode list4 = new ListNode(2);		ListNode list5 = new ListNode(5);				list1.next = list2;		list2.next = list3;		list3.next = list4;		list4.next = list5;				ListNode list = partition(list1, 3);		while(list != null){			System.out.print(list.val+" ");			list = list.next;		}	}	//將鏈表以x為依據分割開來	public static ListNode partition(ListNode head, int x) {		ListNode left = new ListNode();		ListNode tmpLeft = left;				ListNode right = new ListNode();		ListNode tmpRight = right;				if(head == null || head.next == null){			return head;		}				while(head != null){			if(head.val <= x){				ListNode tmp = new ListNode();				tmp.val = head.val;								left.next = tmp;				left = left.next;			}						if(head.val > x){				ListNode tmp = new ListNode();				tmp.val = head.val;								right.next = tmp;				right = right.next;			}					head = head.next;		}				//將左右兩個鏈表進行連接		left.next = tmpRight.next;				return tmpLeft.next;	}	}	------------------------------------------output-------------------------------------------
1 2 2 4 5