Partition List
问题：
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.
思路：
画画图就OK了，基本的链表操作而已
我的代码：
public class Solution { public ListNode partition(ListNode head, int x) { if(head == null) return head; ListNode dummy = new ListNode(-1); dummy.next = head; ListNode pre = dummy; while(head != null) { if(head.val >= x) break; head = head.next; pre = pre.next; } if(head == null) return dummy.next; ListNode tail = pre; while(head != null) { ListNode next = head.next; if(head.val < x) { tail.next = head.next; head.next = pre.next; pre.next = head; pre = head; } else { tail = tail.next; } head = next; } return dummy.next; } }
学习之处：
origPre.next = cur.next; cur.next = pre.next; pre.next = cur;
原文：http://www.cnblogs.com/sunshisonghit/p/4336016.html
