链表划分

/**
 * 链表划分
 * @author buder_cp
 *
 */
public class partitionList {
	public static ListNode partition (ListNode head, int x) {
		ListNode leftHead = new ListNode(0);
		ListNode leftTail = leftHead;
		ListNode rightHead = new ListNode(0);
		ListNode rightTail = rightHead;
		ListNode p = head;			//遍历 原来链表的指针
		while (p != null) {			//向两个链表中插入数值
			if (p.val < x) {
				leftTail.next = p;  //建立指针
				leftTail = p;		//移动指针
			} else {
				rightTail.next = p;
				rightTail = p;
			}
			p = p.next;
		}
		//修改两个链表的指针，改变指向
		leftTail.next = rightHead.next;
		rightTail.next = null;
		return leftHead.next;
	}
	public static void main(String[] args){
		int[] array = {1,4,3,2,5,2};
		int x = 3;
		ListNode head = ListNode.arrayToList(array);
		head = partition(head, x);
		ListNode.printList(head);
	}
}