题目链接: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. For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5. Hide Tags * */ public class PartitionList { public class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } } // 166 / 166 test cases passed. // Status: Accepted // Runtime: 288 ms // Submitted: 1 minute ago //设置两个链表,小于x的节点按顺序链接到less尾部中,大于或等于的节点按顺序链接到greater尾部 //时间复杂度o(n),空间复杂度 o(1) public ListNode partition(ListNode head, int x) { ListNode less = new ListNode(Integer.MAX_VALUE); ListNode greater = new ListNode(Integer.MAX_VALUE); ListNode cur1 = less; ListNode cur2 = greater; while(head != null) { if(head.val < x) { cur1.next = head; cur1 = cur1.next; } else { cur2.next = head; cur2 = cur2.next; } head = head.next; } cur2.next = null; cur1.next = greater.next; return less.next; } public static void main(String[] args) { // TODO Auto-generated method stub } }
原文:http://blog.csdn.net/ever223/article/details/44678957