Find whether two single-linked list have a comon items (b) without additional memory
// Find whether two single-linked list have a comon items (b) without additional memory
let node = function(data) {
this.next = null;
this.data = data;
}
let list = function() {
this.head = null;
}
list.prototype.getLast = function() {
let curr = this.head;
while(curr.next) {
curr = curr.next;
}
return curr;
}
list.prototype.add = function(data) {
if (!this.head) {
this.head = new node(data);
return this.head;
} else {
let curr = this.head;
while(curr.next) {
curr = curr.next;
}
curr.next = new node(data);
return curr.next;
}
}
list.prototype.print = function(name) {
console.log('printing ' + name);
let curr = this.head;
while(curr) {
console.log(curr.data);
curr = curr.next;
}
}
let base = new list();
base.add(0);
base.add(0);
base.add(0);
base.print('base');
let lst1 = new list()
lst1.add(1);
lst1.add(2);
lst1.add(3);
lst1.getLast().next = base.head; //
lst1.print('lst1');
let lst2 = new list()
lst2.add(4);
lst2.add(5);
lst2.add(6);
lst2.getLast().next = base.head; //
lst2.print('lst2');
// main
(() => {
console.log('checking...');
let isShare = function(h1, h2) {
curr1 = h1;
while(curr1) {
curr2 = h2;
while(curr2) {
console.log(curr1.data + ' vs. ' + curr2.data);
if (curr1 == curr2) return true;
curr2 = curr2.next;
}
curr1 = curr1.next;
}
return false;
}
console.log(isShare(lst1.head, lst2.head));
})();
// version 2
// compare last only elements
(() => {
let isShare = function(lst1, lst2) {
return lst1.getLast() === lst2.getLast();
}
console.log(isShare(lst1, lst2));
})();