vadimkorr
3/12/2018 - 1:02 PM

find-if-lists-have-common

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));
})();