Leetcode034--将单链表进行分区

一、原题

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