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.
从左往右扫描，找到第一个大于X的指针，然后再该指针左边，不断插入小于X的元素。这里为了避免处理head是否为空的检测，在头指针位置先插入一个干扰元素，以保证head永不为空，然后在最后返回的时候删除掉
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode partition(ListNode head, int x) { ListNode p = new ListNode(Integer.MIN_VALUE); p.next = head; head = p; ListNode pre = null; while(p != null && p.val < x){ pre = p; p = p.next; } if(p != null){ ListNode cur = pre; while(p != null){ if(p.val < x){ pre.next = p.next; ListNode tmp = cur.next;; cur.next = p; p.next = tmp; cur = cur.next; // 将指针p归位 p = pre; } pre = p; p = p.next; } } return head.next; } }
原文：http://www.cnblogs.com/RazerLu/p/3544416.html