intersection.js

//Write a function to get the intersection point of two Linked Lists.
function intersection(ll1,ll2){
    let c1 = ll1.length()
    let c2 = ll2.length()
    let d = Math.abs(c1-c2)
    if(c1>c2){
        return getIntersection(d,ll1.head,ll2.head)
    }else{
        return getIntersection(d,ll2.head,ll1.head)
    }
}
function getIntersection(d,head1,head2){
    let node1 = head1
    let node2 = head2
    let i=0
    while(i<d){
        if(node1==null)return 
        node1 = node1.next
        i++
    }
    while(node1!=null && node2!=null){
        if(Object.is(node1,node2))return node1.data
        node1 = node1.next
        node2 = node2.next
    }
    return

}

module.exports = intersection

linkedlist.js

/*
pros                             cons
//Dynamic size                  random access not allowed
//ease of insertion/deletion    extra memory space for pointer
*/
let intersection = require('./intersection')

 class Node{
    constructor(data){
        this.data = data
        this.next = null
    }
}
 class LinkedList{

    constructor(data){
        this.head = null
    }

    append(data){
        let node = this.head
        if(node==null){
            this.head = new Node(data)
            return this.head
        }
        while(node.next!=null){
            node = node.next
        }
        node.next = new Node(data)
        return node.next

    }
    push(data){
        let node = this.head
        this.head = new Node(data)
        this.head.next = node
    }

    print(){
        let node = this.head
        while(node!=null){
            console.log(node.data);
            node = node.next
        }
    }
    insertAfter(prevNode,data){
        if(prevNode==null){
            console.log("Previous node can't be null");
            return
        }
        let node = new Node(data)
        node.next = prevNode.next
        prevNode.next = node
    }
    deleteFirst(key){
        let temp = this.head,prev 
        if(temp!=null && temp.data==key){
            this.head =temp.next
            return
        }
        while(temp !=null && temp.data!=key){
            prev = temp
            temp = temp.next
        }
        if(temp==null)return
        prev.next = temp.next
    }
    getMiddle(){
        let fast = this.head
        let slow = this.head
        while(fast!=null && fast.next!=null){
            slow=slow.next
            fast = fast.next.next
        }
        return slow.data

    }
    getFromEnd(n){
        if(this.head==null)return
        let main = this.head
        let ref = this.head
        let count = 0;
        while(count<n){
            if(ref==null)return
            ref = ref.next
            count++
        }
        while(ref!=null){
            main = main.next
            ref = ref.next
        }
        return main.data
    }
    getAt(n){
        let node = this.node,count=0

        while(node!=null){
            if(count==n)return node.data
            count++
            node=node.next
        }
    }
    getCount(key){
        let node = this.head,count=0
        while(node!=null){
            if(node.data==key)count++
            node=node.next
        }
        return count
    }
    deleteList(){
         this.head = null
         return
    }
    deleteAt(pos){
        if(this.head==null)return
        let temp = this.head
        if(pos==0){
            this.head = temp.next
        }
        for(let i=0;temp!=null && i < pos-1;i++)
            temp = temp.next
        
        if(temp==null || temp.next==null)return

        temp.next = temp.next.next
    }
    length(){
        let count = 0
        let node = this.head
        while(node!=null){
            count++ 
            node = node.next
        }
        return count
    }
    getLength(node=this.head){ //recursive
        if(node==null)return 0;
        return 1+this.getLength(node.next)
    }
    swap(key1,key2){
        if(key1==key2)return
        let node1 = this.head,prev1
        while(node1!=null && node1.data != key1){
            prev1 = node1
            node1 = node1.next
        }
        if(node1==null)return

        let node2 = this.head,prev2
        while(node2!=null && node2.data != key2){
            prev2 = node2
            node2 = node2.next
        }
        if(node2==null)return
        if(prev1!=null)prev1.next = node2
        else this.head = node2
        if(prev2!=null)prev2.next = node1
        else this.head = node1

        let temp = node1.next
        node1.next = node2.next
        node2.next = temp
        return
    }
    search(key){
        let node = this.head
        while(node !=null && node.data != key){
            node = node.next
        }
        if(node==null)return false
        return true
    }
    searchRec(key,node=this.head){
        if(node==null)return false
        if(node.data==key)return true
        return this.searchRec(key,node.next)

    }
    hasLoop(){ //floyd algo
        let fast=this.head,slow=this.head
        while(slow && fast && fast.next){
            slow = slow.next
            fast = fast.next.next
            if(Object.is(slow,fast))return true
        }
        return false
    }
    mergeSorted(anotherList){//both list are sorted
        if(this.head==null)return anotherList
        if(anotherList.head==null) return this

        let node1 = this.head
        let node2 = anotherList.head
        let newlist  = new LinkedList()
        if(node1.data<=node2.data){
            newlist.head = new Node(node1.data)
            node1 = node1.next
        }else{
            newlist.head = new Node(node2.data)
            node2 = node2.next
        }
        let tail = newlist.head
        while(1){
            if(node1==null){
                tail.next = node2
                break
            }else if(node2==null){
                tail.next = node1
                break
            }
            if(node1.data<=node2.data){
                tail.next = new Node(node1.data)             
                node1 = node1.next
            }else{
                tail.next = new Node(node2.data)            
                node2 = node2.next 
            }
          tail = tail.next
        }
        return newlist
    }
    //implement this fully
    isPalindrome(){
        let slow=this.head,fast=this.head,prevSlow,mid
        while(slow && fast && fast.next){
            prevSlow=slow
            slow = slow.next
            fast=fast.next
        }
        if(fast!=null){
            mid = slow
            slow = slow.next
        }
        let secondHalf = slow
        prevSlow.next =  null
        reverse(secondHalf)

    }
    reverse(node=this.head){
        let prev = null,current = node,next
        while(current != null){
            next = current.next
            current.next = prev
            prev = current
            current = next
        }
        this.head = prev
    }
    printReverse(node=this.head){
        if(node==null)return
        this.printReverse(node.next)
        console.log(node.data);
    }
    removeDuplicatesSorted(){
        let node = this.head
        while(node && node.next){
            if(node.data==node.next.data){
                let next = node.next.next
                node.next = next
            }else{
                node = node.next
            }            
        }
    }
    removeDuplicatesUnsorted(){
        let map = new Map()
        let node = this.head,prev=null
        while(node){
            if(map.has(node.data)){
                prev.next = node.next
            }else{
                map.set(node.data)
                prev = node
            }
            node = prev.next
        }
    }
}



let ll1 = new LinkedList()