PartitionList [source code]

public class PartitionList {
static
/******************************************************************************/
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode bos = new ListNode (999);
        bos.next = head;
        ListNode lo = bos, i = bos;
        while (i.next != null) {
            if (i.next.val < x) {
                if (i == lo)
                    i = i.next;
                else
                    insertSmaller (lo, i);
                lo = lo.next;
            } else {
                i = i.next;
            }
        }
        return bos.next;
    }

    // insert B.next at the position of A.next
    void insertSmaller (ListNode a, ListNode b) {
        if (a.next == null || b.next == null)
            return;
        ListNode a_next = a.next, b_next = b.next;
        b.next = b_next.next;
        b_next.next = a_next;
        a.next = b_next;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        PartitionList.Solution tester = new PartitionList.Solution();
        int[][] inputs = {
            {5,6,7,0,1,2}, {3}, {0,1,2,5,6,7},
            {2,1},{2},{1,2},
            {2,3,1},{2},{1,2,3},
            {1},{2},{1},
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            ListNode head = ListNode.buildListNode (inputs[3 * i]);
            int x = inputs[3 * i + 1][0];
            String input_str = ListNode.serialize (head);
            System.out.println (Printer.separator ());
            String output_str = ListNode.serialize (tester.partition (head, x)), ans_str = ListNode.serialize (ListNode.buildListNode (inputs[3 * i + 2]));
            System.out.printf ("%s and %d -> %s, expected: %s\n", 
                input_str, x, Printer.wrap (output_str, output_str.equals (ans_str) ? 92 : 91), ans_str
            );
        }
    }
}

看起来就是quick sort的那个partition的要求, 那么问题来了, 这里能用Lomuto的方法, 那个swap的方法来做吗?

当然, 可以直接在旁边collect, 然后最后append到一起也行, 就跟quick sort的partition一样, 有InPlace的做法, 也有out of place的做法;

还是有点想用lomuto来做的, 毕竟是比较slick的一个算法, 而且最近也是刚学过; 不过有点担心的原因是因为LinkedList里面好像swap其实是有点麻烦的;

一开始写的是这个代码:

class Solution {  
    public ListNode partition(ListNode head, int x) {  
        ListNode bos = new ListNode (0);  
        bos.next = head;  
        ListNode lo = bos, i = bos;  
        while (i.next != null) {  
            if (i.next.val < x) {  
                boolean i_can_advance = !(lo.next == i);  
                swapNext (lo, i);  
                i = i_can_advance ? i.next : i;  
                lo = lo.next;  
            } else {  
                i = i.next;  
            }  
        }  
        return bos.next;  
    }  

    void swapNext (ListNode a, ListNode b) {  
        if (a.next == null || b.next == null)  
            return;  
        ListNode a_next = a.next, b_next = b.next;  
        a.next = b_next;  
        b.next = a_next;  
        ListNode a_next_next = a_next.next;  
        a_next.next = b_next.next;  
        b_next.next = a_next_next;  
    }  
}

对应的思路:

注意, 因为LinkedList保留对parent的access很重要, 所以这里的几个指针定义的都是inclusive end, 看下面的例子上面标的invariant范围;

但是这个被test3给break掉了, 因为没有保留相对顺序; 然后仔细研究了一下这个case, 发现一个严重的问题: 没错, LinkedList的swap很难, 这个是因为你根本就不需要在LinkedList里面做swap! 之所以array的时候需要swap是因为array只能这样, 一个人就是一个位置, 没有办法移动; 而LinkedList里面所有人的位置完全是相对的; 在LinkedList里面, 更好的办法实际上就是直接把[i+1]的这个the first of the unprocessed, 直接insert到对应的位置就行了;

最后还是改出来了上面这个版本; 一个思路:

注意, 有两个小细节:

• 当insert成功的时候, 不需要i++, 因为[i+1]刚刚被扔到前面去了, 所以现在的新的[i+1]自动就是the first unprocessed; 这个也跟LinkedList的性质有关系;
• 有一种情况不能insert, 也就是[lo]和[i]之间没有空间的时候, 这个时候加一个小的专门的特殊处理就行了;

最后是速度是1ms (5%), 还行吧, 关键是这个算法设计很有意思;

没有editorial;

https://leetcode.com/problems/partition-list/discuss/29185/Very-concise-one-pass-solution

ListNode *partition(ListNode *head, int x) {  
    ListNode node1(0), node2(0);  
    ListNode *p1 = &node1, *p2 = &node2;  
    while (head) {  
        if (head->val < x)  
            p1 = p1->next = head;  
        else  
            p2 = p2->next = head;  
        head = head->next;  
    }  
    p2->next = NULL;  
    p1->next = node2.next;  
    return node1.next;  
}

out of place的做法, 懒得看了; 如果用这个方法来做, 这个题目根本就是easy难度了;

https://leetcode.com/problems/partition-list/discuss/29183/Concise-java-code-with-explanation-one-pass

the basic idea is to maintain two queues, the first one stores all nodes with val less than x , and the second queue stores all the rest nodes. Then concat these two queues. Remember to set the tail of second queue a null next, or u will get TLE.

public ListNode partition(ListNode head, int x) {  
    ListNode dummy1 = new ListNode(0), dummy2 = new ListNode(0);  //dummy heads of the 1st and 2nd queues  
    ListNode curr1 = dummy1, curr2 = dummy2;      //current tails of the two queues;  
    while (head!=null){  
        if (head.val<x) {  
            curr1.next = head;  
            curr1 = head;  
        }else {  
            curr2.next = head;  
            curr2 = head;  
        }  
        head = head.next;  
    }  
    curr2.next = null;          //important! avoid cycle in linked list. otherwise u will get TLE.  
    curr1.next = dummy2.next;  
    return dummy1.next;  
}

一样的out of place, 大概扫了一眼;

看了top4, 居然都是out of place, 无语了;

submission基本波动;

Problem Description

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.

Difficulty:Medium
Total Accepted:117.6K
Total Submissions:352.9K
Contributor:LeetCode
Related Topics
linked listtwo pointers