一道whatsapp的面试题，求解答！

以下有两个函数，一个是prepend一个node在单链表头之前，第二个函数是产生1 － n的sequence，这个是O(n)的解法了。但面试官要求想个办法比这个解法要快两倍。求大神们帮帮忙啊！

static Node prepend(Node root, int data){
    Node node = new Node(data);
    node.next = root;
    return node;
}

//generate 1 ->2 -> 3 ... -> n   
static Node generateSequence(int n){
    Node node = null;
    for(int i = n; i > 0; i--){
        node = prepend(node, i);
    }
    return node;
}

不太明白。。。就算factor上快两倍也依然是O(n)吧。。。

递归一次 生成两个新节点？

li24yang75 发表于 2015-2-14 04:19
递归一次 生成两个新节点？

我觉得可能是考多线程吧。。。

你这有个问题，每次prepend以后，没重新更新链表的root让他指向新节点

所以每次prepend要执行两次赋值，一句更新新节点的Next指向root，第二句更新root到新节点

如果一次把所有新节点都生成，并且连接好，只把最后一个节点连到当前链表root上，理论上是可以少一半时间的，以为少了一半赋值语句

感觉这么做太简单了点，也许我没get到点上。

silenceleaf 发表于 2015-2-23 11:24
你这有个问题，每次prepend以后，没重新更新链表的root让他指向新节点

所以每次prepend要执行两次赋值， ...

没有 这样不会有效的减少时间。。。所以我最后的解决办法就是用thread

鱼吃鱼翅 发表于 2015-2-24 06:37
没有 这样不会有效的减少时间。。。所以我最后的解决办法就是用thread

多线程（加锁），肯定可以提高2倍的

谁能给一段code 参考一下么... 多谢！！

加锁的话，每次只有一个线程可以对链表进行操作，速度不会增快的。
两个线程，分别构造n/2的链表，然后链起来才可以。

单线程应该不会一半计算量, 多线程 DnC 在合并吧.