Linked List

Question 1

How do you iterate over a linked list?

Answer 1

While (top!= null){ top = top.next }

Question 2

Find value in linked list?

Answer 2

Function findVal(num){ while (top!=null){ if(top.value === num){ return top } } Return false }

Question 3

What is a linked list?

Answer 3

Group of nodes which together represent a sequence. Each node is composed of data and a reference to the next node in the sequence. Linked list has A top or head pointer Last nodes next value points to null

Question 4

How do you add a node/cell to beginning of a linked list?

Answer 4

// create a new node // set node.next = top top = new node

Question 5

How do you add a node/cell to end of linked list if there is a tail pointer?

Answer 5

// create a new node // set new node.next to null top.next = new node (note, only works if there is a tail pointer)

Question 6

How do you add a node/cell to end of linked list if there is not a tail pointer?

Answer 6

while(top.next != null){ top = top.next; } // create a new node // set new node.next to null; top.next = new node;

Question 7

How do insert cell/node after a certain node value?

Answer 7

while(top.next != null){ if(top.next === val){ var temp = top.next; top.next = newNode; newNode.next = temp; } }

Question 8

How do you insert an item into a sorted list?

Answer 8

while(top.next.value

Question 9

How do you copy a linked list?

Answer 9

var newNode = new Node(); while(top.next !== null){ newNode.val = top.val; newNode.next = top.next; top = top.next; }

Question 10

How do you determine if linked list is circular via marking cells?

Answer 10

var is_circular = false; while(top.next !== null){ if(top.next.visited === true){ top.next = null; is_circular = true; } top = top.next; top.is_circular = true; }

Question 11

How do you determine if linked list is circular via hash table?

Answer 11

var obj = {}; while(top.next !== null){ if(obj.hasOwnProperty(top.next)){ top.next = null; return true; } obj[top.next] = top.next; obj[top.visited] = true; top = top.next; return false; }

Question 12

How do you determine if linked list is circular via tortoise and hare?

Answer 12

function hasCycle(linkedList){ var fast = linkedList; var slow = linkedList; var pause = true; while(fast.next){ if(fast === slow){ return true; } if(!pause){ slow = slow.next; } pause = !pause; } return false; }

Question 13

Write function to remove duplicate from an unsorted linked list?

Answer 13

function removeDups(node){
 var ht = {};
 var previous = null;
 while(node !== null){
 if(ht.hasOwnProperty(node.data)){
 previous.next = node.next;
 }
 else{
 ht[node.data] = node.data;
 previous = node;
 }
 node = node.next;
 }
}

Question 14

Impelement an algorithm to find the kth to last element of a singly linked list?

Answer 14

function findKthToLast(head, k){
 var list1 = head
 var list2 = head
 for(var i = 0; i \< k; i++){
 if(list1 === null){
 return null;
 }
 list1 = list1.next;
 }
 while(list1 !== null){
 list1 = list1.next
 list2 = list2.next
 }
 return list2
}

Question 15

Implement an algorithm to delete a node in the middle of singly linked list, given only access to that node?

Answer 15

function deleteMiddleNode(node){
 if(node.next === null || node === null){
 return false;
 }
 node.data = node.next.data;
 node.next = node.next.next;
}

Question 16

Implement a funtion to check if a linked list is a palindrome.

Answer 16

function isPalindrome(node){
 var reversed = [];
 if(node === null){
 return null;
 }
 while(node !== null){
 reversed.push(node);
 node = node.next;
 }
 while(node !== null){
 if(node !== reversed.pop()){
 return false;
 }
 }
 return true;
}

Question 17

Given two singly linked lists, determine if the two lists intersect. Return the intersecting node. Note that the intersection is defined based on referenece, not value. That is, if the kth node of the first linked list is the exact same node (by reference) as the jth node of the second linked list, then they are intersecting.

Answer 17

• get length and tail of each linked list

function findIntersection(list1, list2){
 if(list1 === null || list2 === null){
 return null;
 }
 var result1 = getTailAndSize(list1)
 var result2 = getTailAndSize(list2)

if(result1.tail !== result2.tail){
return null;
}

var difference = Math.abs(result1.size - result2.size)
 var shorter = result1.size \< result2.size ? result1 : result2;
 var longer = result1.size \< result2.size ? result2 : result1;

for(var i = 0; i \< difference; i++){
 longer = longer.next;
 }

while(shorter !== longer){
shorter = shorter.next
longer = longer.next
}
return shorter;
}

function getTailAndSize(list){
 if(list === null){
 return null;
 }
 var list.size = 0;
 while(list !== null){
 list = list.next;
 list.size++;
 }
 list.tail = list;
}

Question 18

Given a circular linked list, implement an algorithm that returns the node at the beginning of the loop?

Answer 18

1. create two pointers, fastpointer and slowpointer
2. move fast pointer at a rate of 2 steps and slowpointer at a rate of 1 step
3. when they collide, move slow pointer to LinkedListHead. Keep fastpointer where it is
4. move slowpointer and fastpointer at a rate of one step. return the new collision point

function beginningOfLoop(head){
 var slow = head;
 var fast = head;
 // find meeting point. this will be loop size - k steps into the linked head
 while(fast !== null && fast.next !== null){
 slow = slow.next
 fast = fast.next.next
 if(slow === fast){
 break;
 }
 }
 // error check -- no meeting point and therefor no loop
 if(fast === null || fast.next === null){
 return null;
 }

// move slow to head. keep fast at meeting point. each are k steps from the loop start. if they
 // move at the same pace, they must meet at loop start
 slow = head;
 while(slow !== fast){
 slow = slow.next
 fast = fast.next
 }
 return fast;
}