# Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

Example 1:

This problem was taken from Leetcode

## Solution

We are not asked to compare the values inside the linked lists but the list node objects, so we could ignore the values of the list.

#### Approach 1: Brute Force

For each node ai in list A, traverse the entire list B and check if any node in list B coincides with ai.

Complexity Analysis

• Time complexity : O(mn).
• Space complexity : O(1).

#### Approach 2: Calculating the length of the two linked lists and compare the elements that could potentially intersect.

• Time complexity : O(m+n).
• Space complexity : O(m) or O(n).
 function ListNode(val) {
this.val = val;
this.next = null;
}

/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/

/**
* @return {ListNode}
*/

let countA = 0;
while(node != null ) {
node = node.next;
countA ++;
}

let countB = 0;
while(node != null ) {
node = node.next;
countB ++;
}

let longList, shortList, diff, iteratorLongLength,iteratorShortLength;
if(countA > countB)
else

let i = 0;
while(shortList != null) {
if(i < diff ) {
longList = longList.next;
}
else {
console.log("long list, short list", longList.val, shortList.val);
if(longList == shortList)
return longList.val;
longList = longList.next;
shortList = shortList.next;
}

i ++;
}
};

console.log (getIntersectionNode(headA, headB) );

what we just did:
– we calculated the length of the first list to be 5 and the second 6 (first and the second loop)
– the third loop is doing two things:
– first since the difference between the shorter and the longer list is 1 we move the cursor to the second element of the longer list (lines 59-61)
– after we position the longer list cursor at the second element we could start comparing (line 64)

If we execute the function we will see this result:

long list, short list 0 4 long list, short list 1 1 long list, short list 8 8

And the third element is exactly where the intersection is.

#### Approach 3: Traverse both lists and when reaching the end of each one, move the pointer to the opposite list and traverse again till intersection is found.

• Time complexity : O(m+n).
• Space complexity : O(m) or O(n).

This basically is the same concept as in the example above, just written in a bit more elegant way.

 function ListNode(val) {
this.val = val;
this.next = null;
}

/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/

/**
* @return {ListNode}
*/

let swapA = false;
let swapB = false;
var i = 0;
while(nodeA != null && nodeB!=null ) {
// node A
if(!swapA && nodeA.next == null) {
swapA = true;
}
else {
nodeA = nodeA.next;
}
// node B
if(!swapB && nodeB.next == null) {
swapB = true;
}
else {
nodeB = nodeB.next;
}

if(nodeA === nodeB)
return nodeA.val;

}
};

console.log (getIntersectionNode(headA, headB) );

what we just did:
– traverse listA and listB till we reach the end of each one (lines 47 and 55) .
– once we reach the end of each list we point the cursor to the opposite list (lines 43 and 51)

#### Approach 4: Hash Table

Traverse list A and store the address / reference to each node in a hash set. Then check every node bi in list B: if bi appears in the hash set, then bi is the intersection node.

Complexity Analysis

• Time complexity : O(m+n).
• Space complexity : O(m) or O(n).
 function ListNode(val) {
this.val = val;
this.next = null;
}

/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/

/**
* @return {ListNode}
*/

let hashMap = {};
while(node != null ) {

hashMap[node.val] = node;
node = node.next;
}

while(node != null) {
let val = node.val;
if(hashMap[val] == node) {
return val;
}
node = node.next;
}
};

console.log ("result: ", getIntersectionNode(headA, headB) );

# LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.put(4, 4);    // evicts key 1
cache.get(3);       // returns 3
cache.get(4);       // returns 4


This problem was taken from Leetcode

## Solution

The brute force solution will be to use array, to push every new element at the top, and on ‘get’ to pop out the element and to put it at the top of the array.

A better solution will be to use hashmap where the element retrieval will be O(1) (constant) but the hashmap is not keeping track of the order of the elements. To solve this problem we are going to link elements in the hashnmap table with double linked list, where each element will point to its previous and next sibling.
On every ‘get’ operation we are going to re-link the element and it’s siblings.

When the cache reaches the capacity we are going to remove the least used node from the bottom.

 put(1,1) put(2,2) get(1) put(3,3) get(2) put(4,4) get(1) get(3) get(4) return 1 -1 -1 3 4 result 1 2,1 1,2 3,1 => (2) 3,1 4,3 => (1) 4,3 3,4 4,3

class LRUCache {

constructor(capacity) {

this.tail = null;
this.capacity = capacity;
this.count = 0;
this.hashMap  = new Map();
}

get(key) {
var node = this.hashMap.get(key);
if(node) {
return node.val;
}
if(this.tail == node && this.tail.prev) {
// if the node is at the tail,
// set tail to the previous node if it exists.
this.tail = this.tail.prev;
this.tail.next = null;
}
if(node.prev)
node.prev.next = node.next;
if(node.next)
node.next.prev = node.prev;
node.prev = null;

return node.val;
}
return -1;
}

put(key, val) {
this.count ++;
var newNode = { key, val, prev: null, next: null };

// this.hashMap is empty creating new node
this.tail = newNode;
}
else {
var oldNode = this.hashMap.get(key);
if(oldNode) {
// if node with the same key exists,
// clear prev and next pointers before deleting the node.
if(oldNode.next) {
if(oldNode.prev)
oldNode.next.prev = oldNode.prev;
else
}
if(oldNode.prev) {
oldNode.prev.next = oldNode.next;
if(oldNode == this.tail)
this.tail = oldNode.prev;
}
// removing the node
this.hashMap.delete(key);
this.count --;
}

// adding the new node and set up the pointers to it's neibouring nodes

if(this.tail == null)

if(this.count == this.capacity + 1) {
// remove last nove if over capacity
var lastNode = this.tail;
this.tail = lastNode.prev;
if(!this.tail) {
//debugger;
}
this.tail.next = null;
this.hashMap.delete(lastNode.key);
this.count --;
}

}
this.hashMap.set(key, newNode);
return null;
}
}

### Singly-linked list example implementation in Java Script

Let’s store these values from the diagram above in linked list.

Using Object:

const list = {
value: 20,
next: {
value: 18,
next: {
value: 15,
next: {
value: 67,
next: null
}
}
}
}
};

/* example of retrieving the value at second position */

console.log(list.head.next); // the result should be 18

Using class

function ListNode(val) {
this.val = val;
this.next = null;
}

/* example of retrieving the last value */
console.log(linkList.next.next.next); // the result should be 67



### Traversing double linked list example

var list  = {
one: {value: 1, prev: null, next: null},
two: {value: 2, prev: null, next: null},
three: {value: 3, prev: null, next: null}
}

var root = list.one;

list.one.next = list.two;
list.two.prev = list.one;
list.two.next = list.three;
list.three.prev = list.two;

var i = 0;

var element = root;
var loop = true;

while(loop == true) {
console.log(">>", element.value);
if(element.next == null)
loop = false;
element = element.next;
}


You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Examples :

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.


This problem was taken from Leetcode

## Solution

The solution:

### Java Script

/**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/

function ListNode(val, next) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}

/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {

function doSum(a,b, carry) {
var result = {
val: 0,
carry: 0
}
var sum = a + b + carry;
if(sum > 9) {
result.val = sum - 10;
result.carry = 1;
}
else {
result.val = sum;
result.carry = 0;
}
return result;
}

var nodeA = l1;
var nodeB = l2;
var end = false;
var carry = 0;
var result = new ListNode(0, null);
var resultPointer = result;
var tmp = null;

while(nodeA != null || nodeB != null) {
var valA = nodeA == null ? 0 : nodeA.val;
var valB = nodeB == null ? 0 : nodeB.val;
var sumResult = doSum(valA, valB, carry);
carry = sumResult.carry;

resultPointer.val = sumResult.val;
resultPointer.next = new ListNode(0, null);
tmp = resultPointer;
resultPointer = resultPointer.next;

nodeA = nodeA ? nodeA.next : null;
nodeB = nodeB ? nodeB.next : null;
}

if(carry != 0) {
tmp.next.val = carry; // add carry to the val of the last node
}
else
tmp.next = null; // remove the last empty node.
return result;
};

var l1 = new ListNode(9,
new ListNode(9,
new ListNode(9,
new ListNode(9, null)
))
);

var l2 = new ListNode(9,
new ListNode(9,
new ListNode(9,
new ListNode(9,
new ListNode(9,
new ListNode(9,
new ListNode(9, null)
)))))
)

// [9,9,9] , [9,9,9,9,9]
// result: [8,9,9,0,0,1]

console.log(result);