Linked Lists

binaryTreeToLinkedList.js

'use strict';

function BinarySearchTree () { 
  this.root = null;
}

function LinkedList () {
    this.head = null;
}

function createLevelLinkedList (root, lists, level) {
  if (root === null) { // base case
    return;
  }

  var list = null;
  if (lists.length === level) {
    list = new LinkedList();
    lists[level] = list;
  } else {
    list = lists[level];
  }

  // http://js-interview.tutorialhorizon.com/2015/10/03/javascript-linked-list-example/
  list.insertNodeAtTail(root.data); 
  
  createLevelLinkedList(root.left, lists, level + 1);
  createLevelLinkedList(root.right, lists, level + 1);
}

// Create a new Balanced Binary Tree as a sample input
// http://js-interview.tutorialhorizon.com/2015/10/12/create-a-binary-search-tree-in-javascript/
var BST = new BinarySearchTree();
var testDate = [8,3,10,1,6,14,4,7];
testData.forEach(el => BST.insertNode(el));

var lists = [];
createLevelLinkedList(BST.root, lists, 0);
console.log('Linked Lists : ', lists);

delete-node.js

'use strict';

function LinkedList () {
    this.head = null;
}

LinkedList.prototype.deleteNode = function (val) {

    if (this.head.data === val) {
        this.head = this.head.next;
    } else {
        var previousNode = this.head;
        var currentNode = previousNode.next;
        while (currentNode) {
            if (currentNode.data === val) {
                previousNode.next = currentNode.next;
                currentNode = currentNode.next;
                break;
            } else {
                previousNode = currentNode;
                currentNode = currentNode.next;
            }
        }
    }
};

// Create an instance of a LinkedList class
var L1 = new LinkedList();

// Create a linked list with six elements
var testData = [5,6,7,8,9,10];
testData.forEach(el => L1.insertNodeAtTail(el));
console.log(L1);

// Delete a head and a tail node
L1.deleteNode(5);
L1.deleteNode(10);
console.log(L1);

// Delete  an intermediate node
L1.deleteNode(7);
console.log(L1);

detectLoop.js

'use strict';

function LinkedList () {
  this.head = null;
}

LinkedList.prototype.hasLoop = function () {
  var p1, p2;
  p1 = this.head;
  p2 = this.head;

  // basic condition for loop to exist
  while (p2.next.next) {
    // console.log('P1 = %d, P2 = %d', p1.data, p2.data);
    p1 = p1.next;
    p2 = p2.next.next;

    if (p1 == p2) {
      return true;
    }
  }
  return false;
};

var L1 = new LinkedList();
var testData = [1,2,3,4,5,6];
testData.forEach(el => L1.insertNodeAtTail(el));

// Create a circular linked list
L1.head.next.next.next.next.next.next = L1.head.next.next;
console.log(L1.hasLoop()); // true

// Remove circular dependency
L1.head.next.next.next.next.next.next = null;
console.log(L1.hasLoop()); // false

ES6-singlyLinkedList.js

class LinkedList {

  constructor() {
    this.head = null;
  }

  insertNodeAtTail(val) {
    var node = {
      data: val,
      next: null
    };

    if (!this.head) {
      this.head = node;
    } else {
      var p1 = this.head;
      while (p1.next) {
        p1 = p1.next;
      }
      p1.next = node;
    }
  }

  deleteNode(val) {
    // If linked list is empty
    if (!this.head) {
      console.log('Linked list is empty.');
      return;
    }
    // if you have to delete the head
    if (this.head.data === val) {
      this.head = this.head.next;
    } else {
      var p1 = this.head;
      var p2 = p1.next;
      while (p2) {
        if (p2.data === val) {
          p1.next = p2.next;
          break;
        } else {
          p1 = p2;
        }
        p2 = p2.next;
      }
    }
  }
}
// Create an instance of a LinkedList class
var L1 = new LinkedList();

// Create a linked list with six elements
var testData = [5,6,7,8,9,10];

testDate.forEach(el => L1.insertNodeAtTail(el));

console.log(L1);

// Delete a head and a tail node
L1.deleteNode(5);
L1.deleteNode(10);
console.log(L1);

// Delete  an intermediate node
L1.deleteNode(7);
console.log(L1);

findLoopLength.js

'use strict';

function LinkedList () {
  this.head = null;
}

LinkedList.prototype.loopLength = function () {
  var isLoop, loopLength;
  var p1, p2;

  isLoop = false;
  loopLength = 1;

  p1 = this.head;
  p2 = this.head;

  while (p2.next.next) {
    p2 = p2.next.next;
    p1 = p1.next;

    if (p1 === p2) {
      isLoop = true;
      break;
    }
  }

  if (isLoop) {
    p2 = p2.next;
    while (p1 !== p2) {
      loopLength++;
      p2 = p2.next;
    }
    return loopLength;
  } else {
    return 0;
  }

};

var L1 = new LinkedList();
var testData = [1,2,3,4,5,6];
testData.forEach(el => L1.insertNodeAtTail(el));

// Create a circular linked list
L1.head.next.next.next.next.next.next = L1.head.next.next;
console.log(L1.loopLength()); // 4

// Remove circular dependency
L1.head.next.next.next.next.next.next = null;
console.log(L1.loopLength()); // 0

isPalindrome.js

'use strict';

function LinkedList () {
    this.head = null;
}

LinkedList.prototype.isPalindrome = function () {
  // Empty or a single element Linked List
  if (!this.head || !this.head.next) {
    console.log('No duplicates were found. Empty or a single element Linked List.');
    return;
  }

  // Create a deep copy of L1 so we can reverse it and compare with L1
  var temp = JSON.stringify(this); // Serialize L1, remember this can be an expensive operation
  var L2 = JSON.parse(temp); // Deserialize L1, remember this can be an expensive operation

  // Object.setPrototypeOf(L2, this); // Change L2's default prototype. This is ES6 Feature. OPTIONAL
  
  L2.reverseLinkedList(); 

  var l2 = L2.head;
  var l1 = this.head;
  
  while (l2) {
    if (l2.data !== l1.data) {
      return false;
    }
    l2 = l2.next;
    l1 = l1.next;
  }

  return true;
};

// Create an instance of a LinkedList class
var L1 = new LinkedList();

// Create a linked list with six elements
L1.insertNodeAtTail(5);
L1.insertNodeAtTail(6);
L1.insertNodeAtTail(7);
L1.insertNodeAtTail(8); 
// L1.insertNodeAtTail(6); 
L1.insertNodeAtTail(9); 
// L1.insertNodeAtTail(5);

console.log(L1.isPalindrome()); // false

// Comment L#36, L#38, L#44 and Uncomment L#37, L#39 to make list palindrome
// console.log(L1.isPalindrome()); // true

kthToLastNode.js

'use strict';

LinkedList.prototype.kthToLastNode = function (k) {
  
  // makes sure the k is positive integer
  if (k <= 0) {
    console.log('Please call the function with positive integer value of k.');
    return;
  }
  
  var p1 = this.head;
  var p2 = this.head;
  
  for (var i = 0; i < k - 1; i++) {
    // this will be true when k is grater than the length of linked list
    if (!p2) {
      console.log('k is greater than the length of the linked list.');
      return;
    }
    p2 = p2.next;
  }
  
  // this will be true when k is the length of linked list
  if (!p2) {
    console.log('k is the size of the linked list.');
    return;
  }
  
  while (p2.next) {
    p1 = p1.next;
    p2 = p2.next;
  }
  
  return p1.data;
};

// Create an instance of a LinkedList class
var L1 = new LinkedList();

// Create a linked list with six elements
var testData = [5,6,7,8,9,10];
testData.forEach(el => L1.insertNodeAtTail(el));
console.log(L1);

console.log(L1.kthToLastNode(3)); // 8
console.log(L1.kthToLastNode(11)); // null
console.log(L1.kthToLastNode(-1)); // null

loopBegining.js

'use strict';

function LinkedList () {
  this.head = null;
}

LinkedList.prototype.loopBegining = function () {
  var p1, p2, isLoop;
  p1 = this.head;
  p2 = this.head;
  
  // loop detection, basic condition for loop to exist
  while (p2.next.next) {
    p1 = p1.next;
    p2 = p2.next.next;

    if (p2 === p1) {
      isLoop = true;
      break;
    }
  }
	
  // Loop begining detection
  if (isLoop) {
    p1 = this.head;
    while (p1 !== p2) {
      p1 = p1.next;
      p2 = p2.next;
    }
    return p1;
  } else {
    return;
  }

};

var L1 = new LinkedList();
var testData = [1,2,3,4,5,6];
testData.forEach(el => L1.insertNodeAtTail(el));

// Create a circular linked list
L1.head.next.next.next.next.next.next = L1.head.next.next;
console.log(L1.loopBegining()); // Object {data: 3, next: Object}

// Remove circular dependency
//L1.head.next.next.next.next.next.next = null;
//console.log(L1.loopBegining());

mergeTwoSortedLists.js

function mergeTwoSortedLists (l1, l2) {

    let mergedLinkedListHead = { val : -1, next : null }; // create dummy node to get started
    let runner = mergedLinkedListHead;

    while(l1 && l2) {
        if(l1.val > l2.val) {
            runner.next = l2;
            l2 = l2.next;
        } else {
            runner.next = l1;
            l1 = l1.next;
        }
        runner = runner.next;
    }

    // l1 = 1->2->3, l2 = 10->20->30
    // In that case l1, will point to null and while loop will break
    // Simply point runner to l2. We do not have to add individual nodes
    runner.next = l1 || l2;

    return mergedLinkedListHead.next;
}

partitionList.js

'use strict';

function LinkedList () {
    this.head = null;
}

LinkedList.prototype.partitionList = function(val) {
  var beforeVal = new LinkedList();
  var afterVal = new LinkedList();
  var p1 = this.head;

  while (p1) {
    if (p1.data < val) {
      beforeVal.insertNodeAtTail(p1.data);
    } else if (p1.data >= val) {
      afterVal.insertNodeAtTail(p1.data);
    }
    p1 = p1.next;
  }

  // merge beforeVal and afterVal LinkedLists
  var p2 = beforeVal.head;
  while (p2.next) {
    p2 = p2.next;
  }
  p2.next = afterVal.head;

  return beforeVal;
};

// Create an instance of a LinkedList class
var L1 = new LinkedList();

// Create a linked list with six elements
var testData = [7,10,5,11,2,4];
testData.forEach(el => L1.insertNodeAtTail(el));

console.log(L1.partitionList(5));

removeDuplicates.js

'use strict';

function LinkedList () {
    this.head = null;
}

LinkedList.prototype.removeDuplicates = function () {
    // Empty or a single element Linked List
    if (!this.head || !this.head.next) {
      console.log('No duplicates were found. Empty or a single element Linked List.');
      return;
    }

    var p1;
    var p2;
    var nodes = {};

    p1 = this.head;
    p2 = p1.next;
    nodes[p1.data] = true;

    while (p2) {
        var data = p2.data;
        if (nodes[data]) {
            p1.next = p2.next;
        } else {
            nodes[data] = true;
            p1 = p2;
        }
        p2 = p2.next;
    }
};

// Base case : No duplicates
var L1 = new LinkedList();
L1.insertNodeAtTail(5);

L1.removeDuplicates();
console.log(L1);

// Two nodes with duplicates
var L2 = new LinkedList();
L2.insertNodeAtTail(5);
L2.insertNodeAtTail(5);

L2.removeDuplicates();
console.log(L2);

// Two nodes without duplicates
var L3 = new LinkedList();
L3.insertNodeAtTail(5);
L3.insertNodeAtTail(6);

L3.removeDuplicates();
console.log(L3);

// Remove duplicates at the end
var L4 = new LinkedList();
L4.insertNodeAtTail(5);
L4.insertNodeAtTail(6);
L4.insertNodeAtTail(7);
L4.insertNodeAtTail(8);
L4.insertNodeAtTail(5);

L4.removeDuplicates();
console.log(L4);

// Remove multiple duplicates from middle
var L5 = new LinkedList();
var testData = [5,6,7,5,5,8];
testData.forEach(el => L5.insertNodeAtTail(el));

L5.removeDuplicates();
console.log(L5);

removeDuplicatesWithoutExtraMemory.js

'use strict';

function LinkedList() {
  this.head = null;
}

LinkedList.prototype.removeDuplicates = function() {
  // Empty or a single element Linked List
  if (!this.head || !this.head.next) {
    console.log('No duplicates were found. Empty or a single element Linked List.');
    return;
  }

  var p1;
  var p2;
  var p3;
  var val;
  p2 = this.head;

  while (p2) {
    val = p2.data;
    p1 = p2;
    p3 = p1.next;

    while (p3) {
      if (p3.data === val) {
          p1.next = p3.next;
      } else {
        p1 = p3;
      }
      p3 = p3.next;
    }

    p2 = p2.next;
  }
};

// Base case : No duplicates
var L1 = new LinkedList();
L1.add(5);

L1.removeDuplicates();
console.log(L1);

// Two nodes with duplicates
var L2 = new LinkedList();
L2.add(5);
L2.add(5);

L2.removeDuplicates();
console.log(L2);

// Two nodes without duplicates
var L3 = new LinkedList();
L3.add(5);
L3.add(5);

L3.removeDuplicates();
console.log(L3);

// Remove duplicates at the end
var L4 = new LinkedList();
var testData = [5,6,7,8,5];
testData.forEach(el => L4.add(el));

L4.removeDuplicates();
console.log(L4);

// Remove multiple duplicates from middle
var L5 = new LinkedList();
var testData = [5,6,7,5,5,8];
testData.forEach(el => L5.add(el));

L5.removeDuplicates();
console.log(L5);

reverseList.js

'use strict';

function LinkedList () {
    this.head = null;
}

LinkedList.prototype.reverseLinkedList = function () {

  // Empty or a single element Linked List
  if (!this.head || !this.head.next) {
    console.log('No duplicates were found. Empty or a single element Linked List.');
    return;
  }
  
  var p1 = null;
  var p2 = this.head;
  var p3;

  while (p2) {
    p3 = p2.next;
    p2.next = p1;
    p1 = p2;
    p2 = p3;
  }

  this.head = p1;
}

// Base case : Zero nodes
var L1 = new LinkedList();

L1.reverseLinkedList();
console.log(L1);

// Single node
var L2 = new LinkedList();
L2.insertNodeAtTail(5);

L2.reverseLinkedList();
console.log(L2);

// Two nodes 
var L3 = new LinkedList();
L3.insertNodeAtTail(5);
L3.insertNodeAtTail(6);

L3.reverseLinkedList();
console.log(L3);

// Generic case
var L4 = new LinkedList();
var testData = [5,6,7,8,5];
testData.forEach(el => L4.insertNodeAtTail(el));

L4.reverseLinkedList();
console.log(L4);

singlyLinkedList.js

'use strict';

function LinkedList () {
    this.head = null;
}

LinkedList.prototype.insertNodeAtTail = function (val) {
    var node = {
        data: val,
        next:null
    };

    if (!this.head) {
        this.head = node;
    } else {
        var p1 = this.head;
        while (p1.next) {
            p1 = p1.next;
        }
        p1.next = node;
    }
};

LinkedList.prototype.deleteNode = function (val) {
    // If linked list is empty
    if (!this.head) {
      console.log('Linked list is empty.');
      return;
    }
    // if you have to delete the head
    if (this.head.data === val) {
        this.head = this.head.next;
    } else {    
      var p1 = this.head;
      var p2 = p1.next;
      while (p2) {
        if (p2.data === val) {
            p1.next = p2.next;
            break;
        } else {
            p1 = p2;
        }
        p2 = p2.next;
      }
    }
};

// Create an instance of a LinkedList class
var L1 = new LinkedList();

// Create a linked list with six elements
var testData = [5,6,7,8,9,10];
testData.forEach(el => L1.insertNodeAtTail(el));
console.log(L1);

// Delete a head and a tail node
L1.deleteNode(5);
L1.deleteNode(10);
console.log(L1);

// Delete  an intermediate node
L1.deleteNode(7);
console.log(L1);

These are awesome - thanks for sharing!

@youngfreezy Good set of linked list related problems are solved here http://js-algorithms.tutorialhorizon.com/category/linked-list/