对js的链表操作


原题目链接

这是我今天连续更新四篇的原因，一部分是因为最近有点事，一部分是因为这个东西耗了我太多精力了（所以之前都没有更新），大概有多耗费精力呢？我觉得js的引用类型每个人都应该来那么一下。
不是数组的引用类型，是使用链表的时候的引用类型，最近做的我很感动！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

/**
 * Created by YangSir on 2016/11/8.
 */
class ListNode{
    val:number;
    next:ListNode;
}
var addNode = function(List:ListNode,val:number, pos?:number){
    var L = List;
    if(L.val == undefined){
        L.val = val; L.next = null;
        return;
    }else{
        if(L.next){
            addNode(L.next, val, pos-1);
        }else{
            L.next = new ListNode();
            L.next.val = val;
            L.next.next = null;
            return ;
        }
    }
};
var mergeKLists = function(lists:Array<ListNode>){
    //var k = lists.length;
    var Arr = [];
    var min = -1, index;
    var newList = new ListNode();
    while(true){
        min = lists[0].val; index = 0;
        for(var i = 0, k = lists.length; i < k ; i++){
            var flag = 0;
            if(lists[i]||lists[i].val){
                var val = lists[i].val;
                if(min>val){
                    min = val;
                    index = i;
                }
            }
        }
        addNode(newList, min);
        if(lists[index]){   //如果存在就执行向下延伸并且各项指标加一，如果next不存在就删掉当前各项指标
            Arr[index] ? Arr[index]++ : Arr[index] = 0;
            if(lists[index].next){
                lists[index] = lists[index].next;
            }else{
                Arr.splice(index, 1);
                lists.splice(index, 1);
                if(lists.length == 0){
                    return newList;
                }
            }
        }
    }
};
//下面是测试使用的数据
var L = new ListNode();
var M = new ListNode();
var Arr = [];
Arr.push(M);
Arr.push(L);
for(var i = 0; i < 7; i++){
    if(i%2){
        addNode(L, i);
    }else{
        addNode(M, i);
    }
}
console.log(L,M,Arr);
var newL = mergeKLists(Arr);
console.log(newL);