[第二轮] 2/25-3/3 CareerCup 2.4

https://github.com/1094401996/Ca ... /PartitionList.java

* 运用了快排的partition思想，方法在链表类这中提供。。。。

不用新建链表，直接在原链表上操作：把<x的node移到List的最前面。O(n) time, O(1) space

        public static ListNode partition(ListNode head, int x) {
                ListNode node = head;
                while (node != null) {
                        if (node.getValue() < x) {
                                head = appendToHead(head, node.getValue());
                                removeNode(node);
                        } else {
                                node = node.getNext();
                        }
                }
                return head;
        }

        public static ListNode appendToHead(ListNode head, int value) {
                ListNode addNode = new ListNode(value);
                addNode.setNext(head);
                head = addNode;
                return head;
        }

        public static void removeNode(ListNode node) {
                node.setValue(node.getNext().getValue());
                node.setNext(node.getNext().getNext());
        }

grassgigi 发表于 2013-2-26 13:50
我打错了.那个方法是partition，不是pivot，应该就在算法导论quicksort刚开始的地方。。

我的代码有点 ...

那如果LinkedList里面有两个数和当前函数给的参数一样怎么处理呢？

我已开始也想到的是用QuickSort里面的partition，但是发现好像碰到参数和value一样的情况就会有问题