Partition List (Java)

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.

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

	/*
	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.
	For example,
	Given 1->4->3->2->5->2 and x = 3,
	return 1->2->2->4->3->5.
	*/
	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) {
	* val = x;
	* next = null;
	* }
	* }
	*/
	public class PartitionList {
	public ListNode partition(ListNode head, int x) {
	if (head==null || head.next==null){
	return head;
	}
	// leftSide
	ListNode preLeftHead=new ListNode (-1);
	ListNode leftEnd=preLeftHead;
	// rightSide
	ListNode preRightHead=new ListNode(-1);
	ListNode rightEnd=preRightHead;
	ListNode run=head;
	while (run!=null){
	ListNode temp=run.next;
	if (run.val<x){
	leftEnd.next=run;
	leftEnd=leftEnd.next;
	}
	else{
	rightEnd.next=run;
	rightEnd=rightEnd.next;
	}
	run.next=null;
	run=temp;
	}
	// connect left and right
	leftEnd.next=preRightHead.next;
	return preLeftHead.next;
	}
	}

view raw PartitionList.java hosted with ❤ by GitHub