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.
O(1) 的空间 O(n)的时间复杂度
public class Solution { public ListNode partition(ListNode head, int x) { if(head==null||head.next==null) return head; ListNode root = head; ListNode less = head; ListNode re = head; if(head.val>=x){ ListNode tt = new ListNode(0); root = tt; ListNode pre = root; root.next=head; while(less!=null){ if(less.val>=x){ pre=pre.next; less=less.next; continue; } ListNode temp = new ListNode(less.val); temp.next=root.next; root.next=temp; root=temp; pre.next=less.next; less=pre.next; } re=tt.next; }else{ root=head; ListNode pre=head; less=head.next; while(less!=null){ if(less.val>=x){ pre=pre.next; less=less.next; continue; } ListNode temp = new ListNode(less.val); //需要特殊注意的地方 特殊case [1,1] 2 if(root==pre){ root=root.next; pre=pre.next; less=less.next; }else{ temp.next=root.next; root.next=temp; root=temp; pre.next=less.next; less=pre.next; } } } return re; } }
【LeetCode】Partition List,布布扣,bubuko.com
原文：http://www.cnblogs.com/yixianyixian/p/3736525.html