http://blog.welkinlan.com/2015/11/12/partition-list-leetcode-java-2/
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.
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
return
Given
1->4->3->2->5->2 and x = 3,return
1->2->2->4->3->5.
The key is to use fake header, one includes all smaller nodes, another includes all equal or greater nodes.
You should preserve the original relative order of the nodes in each of the two partitions.
http://blog.welkinlan.com/2015/11/12/partition-list-leetcode-java-2/
public ListNode partition(ListNode head, int x) {
if (head == null) return null;
ListNode helper = new ListNode(0);
helper.next = head;
ListNode last = helper; //last node of all elements less than x
ListNode pre = helper; //pre node
while (pre.next != null){
if (pre.next.val < x){
if (walker != pre){
ListNode next = pre.next.next;
pre.next.next = last.next;
last.next = pre.next;
pre.next = next;
}
else { //all elements up to now are less than x
pre = pre.next;
}
last = last.next; //update last
}
else {
pre = pre.next;
}
}
return helper.next;
}
X. http://www.cnblogs.com/springfor/p/3862392.html
new两个新链表，一个用来创建所有大于等于x的链表，一个用来创建所有小于x的链表。
遍历整个链表时，当当前node的val小于x时，接在小链表上，反之，接在大链表上。这样就保证了相对顺序没有改变，而仅仅对链表做了与x的比较判断。
最后，把小链表接在大链表上，别忘了把大链表的结尾赋成null。
1 public ListNode partition(ListNode head, int x) {2 if(head==null||head.next==null)
3 return head;
4
5 ListNode small = new ListNode(-1);
6 ListNode newsmallhead = small;
7 ListNode big = new ListNode(-1);
8 ListNode newbighead = big;
9
10 while(head!=null){
11 if(head.val<x){
12 small.next = head;
13 small = small.next;
14 }else{
15 big.next = head;
16 big = big.next;
17 }
18 head = head.next;
19 }
20 big.next = null;
21
22 small.next = newbighead.next;
23
24 return newsmallhead.next;
25 }
http://www.jiuzhang.com/solutions/partition-list/
public ListNode partition(ListNode head, int x) { if (head == null) { return null; } ListNode leftDummy = new ListNode(0); ListNode rightDummy = new ListNode(0); ListNode left = leftDummy, right = rightDummy; while (head != null) { if (head.val < x) { left.next = head; left = head; } else { right.next = head; right = head; } head = head.next; } right.next = null; left.next = rightDummy.next; return leftDummy.next; }
public ListNode partition(ListNode head, int x) {
if (head==null || head.next==null){return head;}// leftSideListNode preLeftHead=new ListNode (-1);ListNode leftEnd=preLeftHead;// rightSideListNode 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 rightleftEnd.next=preRightHead.next;return preLeftHead.next;}
Another solution from http://www.darrensunny.me/leetcode-partition-list/
public ListNode partition(ListNode head, int x) {
if (head == null)
return null;
// Use a sentinel to avoid boundary check
ListNode sentinel = new ListNode(0);
sentinel.next = head;
// Find the node whose next is the first one not smaller than x
ListNode preFirstLarger = sentinel;
while (preFirstLarger.next != null && preFirstLarger.next.val < x)
preFirstLarger = preFirstLarger.next;
if (preFirstLarger.next == null)
return head;
// Each time we meet a node smaller than x, we move it to before the first
// one not smaller than x
ListNode pre = preFirstLarger.next, current = pre.next;
while (current != null) {
if (current.val < x) {
pre.next = current.next;
current.next = preFirstLarger.next;
preFirstLarger.next = current;
preFirstLarger = preFirstLarger.next;
current = pre.next;
} else {
pre = current;
current = current.next;
}
}
return sentinel.next;
}
Partition: Write code to partition a linked list around a value x, such that all nodes less than x come
before all nodes greater than or equal to x. If x is contained within the list the values of x only need
to be after the elements less than x (see below). The partition element x can appear anywhere in the "right partition"; it does not need to appear between the left and right partitions
LinkedListNode head = node;
LinkedListNode tail = node;
/* Partition list */
while (node != null) {
LinkedListNode next = node.next;
if (node.data < x) {
/* Insert node at head. */
node.next = head;
head = node;
} else {
/* Insert node at tail. */
tail.next = node;
tail = node;
}
node = next;
}
tail.next = null;
return head;
}
LinkedListNode beforeStart = null;
LinkedListNode beforeEnd = null;
LinkedListNode afterStart = null;
LinkedListNode afterEnd = null;
/* Partition list */
while (node != null) {
LinkedListNode next = node.next;
node.next = null;
if (node.data < x) {
if (beforeStart == null) {
beforeStart = node;
beforeEnd = beforeStart;
} else {
beforeEnd.next = node;
beforeEnd = node;
}
} else {
if (afterStart == null) {
afterStart = node;
afterEnd = afterStart;
} else {
afterEnd.next = node;
afterEnd = node;
}
}
node = next;
}
/* Merge before list and after list */
if (beforeStart == null) {
return afterStart;
}
beforeEnd.next = afterStart;
return beforeStart;
}
public static LinkedListNode partition(LinkedListNode node, int x) {
LinkedListNode beforeStart = null;
LinkedListNode afterStart = null;
/* Partition list */
while (node != null) {
LinkedListNode next = node.next;
if (node.data < x) {
/* Insert node into start of before list */
node.next = beforeStart;
beforeStart = node;
} else {
/* Insert node into front of after list */
node.next = afterStart;
afterStart = node;
}
node = next;
}
/* Merge before list and after list */
if (beforeStart == null) {
return afterStart;
}
LinkedListNode head = beforeStart;
while (beforeStart.next != null) {
beforeStart = beforeStart.next;
}
beforeStart.next = afterStart;
return head;
}
Read full article from My Leetcode: Partition List (Java)
