2014年11月24日

[nunnly]

现在，我们有一个单向链表，空的表我们用null表示。非空链表我们用两个元素的数组组成[value, tail]。

例如值为1，2，3的列表表示为[1, [2, [3, null]]]

你的任务是开发一个函数reverseList 返回新的指定链表的反向链表，并且不修改原链表。

注：请确保你的解决方案适用于大型的链表。

function reverseList(list) {
  // TODO: Your awesome code here
}

//reverseList(null) => null
//reverseList([1, [2, [3, null]]])  => [3, [2, [1, null]]]

[scarletcc]

function reverseList(list) {
    if(list == null) {
        return list;
    }
    var arrList = list.toString().split(',');
    var ret = null;
    for(var i=0; i<arrList.length-1; i++) {
        var arr = [arrList[i], ret];
        ret = arr;
    }
    return ret;
}

这样可以吧？

[XadillaX]

function reverseList(list) {
    if(!list) return null;
    var last = null;
    for(var node = list, pre = null; node !== null; pre = node, node = node[1]) node.push(pre), last = node;
    for(var p = list, l = last; p.length + l.length === 6;) {
        if(p === l) return p.pop(), list;
        p[2] = p[0], p[0] = l[0], l[0] = p[2];
        p.pop(), l = l[2], l[1].pop(), p = p[1];
    }

    return list;
}

console.log(reverseList(null)) //=> null
console.log(reverseList([1, [2, [3, null]]])) //=> [3, [2, [1, null]]]

代码挫了点，不过也算是 O(n) 的了。

好吧，又因为歧义返回原链表指针了。

[XadillaX]

@scarletcc 你的类型变了，数字变成字符串了。

另：

console.log(reverseList(["1", [true, [{a:"b"}, null]]]))

你的跑挂了。

[scarletcc]

function reverseList(list) {
    if(list == null) {
        return list;
    }
    //var arrList = list.toString().split(',');
    var first = list[0], next = list[1], arrList = [];
    while(next != null) {
        arrList.push(first);
        first = next[0];
        next = next[1];
    }
    arrList.push(first);

    var ret = null;
    for(var i=0; i<arrList.length; i++) {
        var arr = [arrList[i], ret];
        ret = arr;
    }
    return ret;
}

修改了一下，之前偷懒直接用list.toString()，没考虑到类型问题 - -！

[XadillaX]

function reverseList(l) {
    for(var p = l, r = null; p; r = [ p[0], r ], p = p[1]);
    return r;
}

好吧根据题目原意再做一遍吧 -。 -

[businiaowa]

function reverseList(list) {
    if(!list) return null;
    var next = list, 
        result = [next[0], null];

    while(next = next[1]) {
        result = [next[0], result];
    }
    return result;  
}

[XadillaX]

@businiaowa 你没考虑 list 是 null 的情况。

[businiaowa]

@XadillaX 是的！已修正

[businiaowa]

@XadillaX function reverseList(l) { for(var p = l, r = null; p; r = [ p[0], r ], p = p[1]); return r; } 这样读起来会不会困难啊 额 可能你随便写的名字

[XadillaX]

@businiaowa l 是 list，p 是 pointer，r 是 result。