1var assert = require('assert');
2
3function mergeLists(arrOfLists) {
4  if (!arrOfLists || arrOfLists.length === 0) {
5    return [];
6  }
7
8  let pq = new PriorityQueue();
9  for (let list of arrOfLists) {
10    if (list) {
11      let currentNode = list;
12      pq.insert(currentNode.val);
13
14      while (currentNode.next) {
15        pq.insert(currentNode.next.val);
16        currentNode = currentNode.next;
17      }
18    }
19  }
20  return pq.first || [];
21}
22
23// Supporting data structures
24
25class PriorityQueue {
26  constructor() {
27    this.first = null;
28    this.size = 0;
29  }
30
31  insert(val) {
32    const newNode = new Node(val);
33    if (!this.first || newNode.val < this.first.val) {
34      newNode.next = this.first;
35      this.first = newNode;
36    } else {
37      let currNode = this.first;
38
39      while (currNode.next && newNode.val > currNode.next.val) {
40        currNode = currNode.next;
41      }
42      newNode.next = currNode.next;
43      currNode.next = newNode;
44    }
45  }
46}
47
48function Node(val) {
49  this.val = val;
50  this.next = null;
51}
52
53class LinkedList {
54  constructor() {
55    this.head = null;
56    this.tail = null;
57  }
58
59  prepend(newVal) {
60    const currentHead = this.head;
61    const newNode = new Node(newVal);
62    newNode.next = currentHead;
63    this.head = newNode;
64
65    if (!this.tail) {
66      this.tail = newNode;
67    }
68  }
69
70  append(newVal) {
71    const newNode = new Node(newVal);
72    if (!this.head) {
73      this.head = newNode;
74      this.tail = newNode;
75    } else {
76      this.tail.next = newNode;
77      this.tail = newNode;
78    }
79  }
80
81  isPresent(val) {
82    let head = this.head;
83    while (head) {
84      if (head.val === val) {
85        return true;
86      }
87      head = head.next;
88    }
89    return false;
90  }
91
92  toArray() {
93    const toPrint = [];
94    let currNode = this.head;
95    while (currNode) {
96      toPrint.push(currNode.val);
97      currNode = currNode.next;
98    }
99    return toPrint;
100  }
101
102  toString() {
103    const toPrint = [];
104    let currNode = this.head;
105
106    while (currNode) {
107      toPrint.push(currNode.val);
108      currNode = currNode.next;
109    }
110
111    return toPrint.join(' -> ');
112  }
113}
114
115try {
116  const ll1 = new LinkedList();
117  ll1.append(2);
118  ll1.append(6);
119  ll1.append(9);
120  const ll2 = new LinkedList();
121  ll2.append(1);
122  ll2.append(2);
123  ll2.append(7);
124  const ll3 = new LinkedList();
125  ll3.append(2);
126  ll3.append(6);
127  ll3.append(10);
128  let final = mergeLists([ll1.head, ll2.head, ll3.head]);
129  let finalResult = [];
130  const result = [1, 2, 2, 2, 6, 6, 7, 9, 10];
131  while (final) {
132    finalResult.push(final.val);
133    final = final.next;
134  }
135  for (let i = 0; i < result.length; i++) {
136    assert.equal(finalResult[i], result[i]);
137  }
138
139  console.log(
140    'PASSED: Expect `mergeLists(2 -> 6 -> 9, 1 -> 2 -> 7, 2 -> 6 -> 10)` to return 1 -> 2 -> 2 -> 2 -> 6 -> 6 -> 7 -> 9 -> 10'
141  );
142} catch (err) {
143  console.log(err);
144}
145
146try {
147  const ll1 = new LinkedList();
148  ll1.append(3);
149  ll1.append(4);
150  const ll2 = new LinkedList();
151  ll2.append(1);
152  ll2.append(2);
153  ll2.append(7);
154  let final = mergeLists([ll1.head, ll2.head]);
155  let finalResult = [];
156  const result = [1, 2, 3, 4, 7];
157  while (final) {
158    finalResult.push(final.val);
159    final = final.next;
160  }
161  for (let i = 0; i < result.length; i++) {
162    assert.equal(finalResult[i], result[i]);
163  }
164
165  console.log(
166    'PASSED: Expect `mergeLists(3 -> 4, 1 -> 2 -> 7)` to return 1 -> 2 -> 3 -> 4 -> 7'
167  );
168} catch (err) {
169  console.log(err);
170}