[js] 实现单向链表数组的反向接口

[VaJoy]

我们想通过数组来体现单向链表间的关系。 对于空的表我们直接用 null 表示。非空链表则用带两个元素的数组[value, tail]来表示。

例如值为1 -> 2 -> 3（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]]]

[bluesrocker]

function reverseList(list){
    var reList = null;
    if( list===null || typeof list === "undefined" ){
        return reList;
    }
    if( !(Object.prototype.toString.call(list)==='[object Array]') || 
         list.length<2 ) {
        throw new TypeError(list + '不是合法的数组形式的链表'); //第0链
    }
    var flatArr = [];
    if(list.length>=2){
        var tail = list;
        var leng = 0;
        var value;
        do{
            ++leng;
            if( (!(Object.prototype.toString.call(tail[1])==='[object Array]') || 
                   tail[1].length<2) && tail[1] !== null ){
                    throw new TypeError((list) + '的第' + (leng) + '链不是合法的数组形式的链表');
            }

            value = tail[0];
            tail = tail[1];
            flatArr.push(value);
        }while(tail !== null);
        reList = [flatArr.shift(), null];
        while(flatArr.length>0){
            reList = [flatArr.shift(), reList];
        }
    }
    return reList;
}

[horsefefe]

function reverseList(list){
    if(!(Object.prototype.toString.call(list)==='[object Array]') || 
         list.length<2 ) {
        throw new TypeError(list + '不是合法的数组形式的链表');
    }
    var last_arr=[];
    var result=[];
    var i=0;
    while(list.length==2&&list[1]!=null&&list[1].length==2){
        if(i==0){
            i++;
            last_arr=[i,null];
        }else{
            var new_arr=[];
            new_arr.push(list[0]);
            new_arr.push(last_arr);
            last_arr=new_arr;
            i++;
        }
        list=list[1];
    }
    result.push(list[0]);
    result.push(last_arr);
    return result;
}

[LeoHuiyi]

function getList(num, f, arr) {
    if (num > 0) {
        num--;
        f++;
        return [f, getList(num, f, arr)];
    } else {
        return null;
    }
}

function reverseList(list) {
    var listArr = [];

    function _reverseList(list, f){
        if(list){
            _reverseList(list[1], list[0]);

        }

        getList(f);
    }

    function getList(num){
        if(num){
            getList.arr[0] = num;
            getList.last = getList.arr;
            getList.arr = getList.arr[1] = [];
        }else{
            getList.last[1] = null;
        }
    }

    getList.arr = listArr;

    _reverseList(list);

    return listArr;
}

var list = getList(3, 0, []);

console.log(list); //[1, [2, [3, null]]]

console.log(reverseList(list));

[wanglianjie91]

function reverseList(list){
    var list1 = list.slice(0);
    var arr = [];
    var i = 0;
    (function(list){
        if(list[1] === null){
            arr[i] = list[0];
            return;
        }
        arr[i] = list[0];
        i++;
        return arguments.callee(list[1]);
    })(list1);

    arr.reverse();
    var Len = arr.length;
    var newList = [];
    var j = 0;
    (function(list){
        if(j === Len-1){
            list[0] = arr.shift();
            list[1] = null;
            return ;
        }
        j++;
        list[0] = arr.shift();
        list[1] = [];
        return arguments.callee(list[1]);
    })(newList)

    return newList;
}