9 Javascript Beginner Level Linked Lists Interview Questions & Answers
Below is a list of our Javascript Beginner Level Linked Lists interview questions. Click on any interview question to view our answer advice and answer examples. You may view 5 answer examples before our paywall loads. Afterwards, you'll be asked to upgrade to view the rest of our answers.
1. Add two numbers from two separated singly-linked lists.
This interview question focuses on JavaScript linked lists and values along with constraints.
You are given two numbers that are represented as two singly-linked lists. Each node of the linked list represents a digit in the number. The digits are stored in reverse order. That is, the unit-place digit is the head of the linked list. Your task is to find the sum of the two numbers and return the result in the form of a linked list.
/* Example */
The two numbers are 123 and 456
so the given linked lists will be
3 -> 2 -> 1 and 6 -> 5 -> 4
The sum of the numbers is 579
So the expected result will be
9 -> 7 -> 5
/* Constraints */
The numbers of nodes in each given linked lists will be between 1 and 100Solution:
The first solution that comes to mind is to get the value numbers from the given linked lists. Then add them together and create a linked list from the result.
One constraint is the number of the digits in the list is up to 100, which means the range of the numbers is [1, 10100], which is too large for storing numbers directly in their bit forms in a computer.
What we can do is take digits one by one from the linked lists and add them. If it is smaller than 10, directly append it to the resultant list; if it is greater than 10, then append its unit place to the list and forward carry 1 to the next digits as we do in pen-paper while adding two numbers.
More formally,
Let, a and b are the linked lists and res be result list.
ai and bi are digits stored in the ith node.
ri = ai + bi + ci - 1 // take carry from last calculation
resi = ri % 10 // store the unit place i.e. remainder by 10
ci = floor(ri / 10) // forward carry, if any
class ListNode {
constructor(val, next) {
this.val = val || 0
this.next = next || null
}
}
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
function addTwoNumbers(l1, l2) {
// create a dummy node
const res = new ListNode(0)
let carry = 0
let a = l1
let b = l2
let currRes = res
while(a != null || b != null) {
// if either a or b are null i.e. length of one number
// is greater than other, then assume(extend) 0
// at other places
const digitA = (a && a.val) || 0
const digitB = (b && b.val) || 0
const r = digitA + digitB + carry
const node = new ListNode(r % 10)
carry = Math.floor(r / 10)
currRes.next = node
currRes = currRes.next
a = a && a.next
b = b && b.next
}
// if there is carry at the end. It means
// addition of most significant digits of given numbers
// is greater than 10. E.g a = 999, b = 999
if (carry > 0) {
const node = new ListNode(carry)
currRes.next = node
}
return res.next
};
Time complexity - O(max(n, m)) // n and m are length of the two digits
Space complexity - O(1)
Written by S. Kumar on May 5th, 2021
2. Return the middle node of a given linked list.
This interview question concentrates on using JavaScript methods and linked lists.
You are given a linked list. You need to return the middle node of the linked list. If there are two middle nodes (the list is of even size), then return the second node.
/* Example */
Given list- 1 -> 2 -> 3 -> 4 -> 5
expected returned node- 3
Given list- 1 -> 2 -> 3 -> 4 -> 5 -> 6
expected returned node- 4
Solution:
The solution is quite simple. We will count the total number of nodes in the list. Then we will find the index of the middle element by dividing it by 2.
Let nodeCount be total number of nodes
if nodeCount is odd,
middle element is at index floor(nodeCount / 2)
for example, if nodeCount = 5, middle element element is at index floor(5 / 2) = 2
if nodeCount is even,
middle element is at index nodeCount / 2
for example, if nodeCount = 6, middle element element is at index 6 / 2 = 3
class ListNode {
constructor(val, next) {
this.val = val || 0
this.next = next || null
}
}
/**
* @param {ListNode} head
* @return {ListNode}
*/
function findMiddleElement(head) {
if (!head) return null
let nodeCount = 0
let curr = head
while(curr !== null) {
nodeCount++
curr = curr.next
}
let mid = Math.floor(nodeCount / 2)
curr = head
for (let i = 1; i <= mid; i++) {
curr = curr.next
}
return curr
}Time complexity - O(nodeCount)
Space complexity - O(1)
Written by S. Kumar on May 5th, 2021
3. Remove elements from linked list that are equal to target.
This interview question shows the developer's ability to use JavaScript recursion and iteration.
You are given the head of a linked list. You are also given a target value. Your task is to remove all the nodes from the linked list whose value is equal to the target.
/*Example*/
Given:- linked list => 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 target = 6
Expected output:- 1 -> 2 -> 3 -> 4 -> 5Solution:
Approach I (recursive):
In the recursive approach, we will check the value of the current node in the function call. If the value of the current node i.e. head in the function call is equal to target, we return next of head instead of returning head. Before doing that, we recursively check and remove the next of head. For example:- for list 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6, the calls are:
(rm denotes the function removeElements)
|rm(1)
| |rm(2)|
| | |rm(6)|
| | | |rm(3)|
| | | | |rm(4)|
| | | | | |rm(5)|
| | | | | | |rm(6)|
| | | | | | | |rm(null)
| | | | | | | | return null
| | | | | | | |head.next = null
| | | | | | | |head.val == 6; // 6 == 6 => true
| | | | | | | |return head.next(null)
| | | | | | |head.next = null
| | | | | | |head.val == 6; // 5 == 6 => false
| | | | | | |return head(5)
| | | | | |head.next = 5
| | | | | |head.val == 6 // 4 == 6 => false
| | | | | |return head(4)
| | | | |head.next = 4
| | | | |head.val == 6 // 3 == 6 => false
| | | | |return head(3)
| | | |head.next = 3
| | | |head.val == 6 // 6 == 6 => true
| | | |return head.next(3)
| | |head.next = 3
| | |head.val == 6 // 2 == 6 => false
| | |return head(2)
| |head.next = 2
| |head.val == 6 // 1 == 6 => false
| |return head(1)
The resulting list is the return of all the function calls i.e. 1 -> 2 -> 3 -> 4 -> 5
class ListNode {
constructor(val, next) {
this.val = val || 0
this.next = next || null
}
}
/**
* @param {ListNode} head
* @param {number} target
* @return {ListNode}
*/
function removeElements(head, target) {
if (head === null) return null
head.next = removeElements(head.next, val)
return head.val === target ? head.next : head
}n = length linked list
Time complexity- O(n)
Space complexity- O(n)
Approach II (iterative):
In the iterative approach, we loop over all the nodes in the list. From the current node curr, if it has a next node (curr.next) and its value is equal to the target, we will remove the next node. To remove we will set the next of curr to the next of curr.next.
After the loop, all the nodes with value target will be removed except at the head. So after the loop, we will check for the head node too.
class ListNode {
constructor(val, next) {
this.val = val || 0
this.next = next || null
}
}
/**
* @param {ListNode} head
* @param {number} target
* @return {ListNode}
*/
function removeElements(head, target) {
if (head === null) return null
let curr = head
while(curr !== null && curr.next !== null) {
if (curr.next.val === target) {
curr.next = curr.next.next
} else {
curr = curr.next
}
}
// the first node
if (head.val === target) head = head.next
return head
}n = length linked list
Time complexity- O(n)
Space complexity- O(1)
Written by S. Kumar on May 5th, 2021
4. Delete the node in a singly-linked list.
This question focuses on JavaScript iteration.
You are given a node nodeToDelete of a singly linked list. Your task is to delete this node. This is guaranteed that the given node will not be the tail node of the linked list. Please note that you are not given the head of the linked list. You don’t have to return anything, just update the list in place.
/*Example*/
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
|
given node
Expected output list:- 1 -> 2 -> 4 -> 5 -> 6 -> 7Solution:
We will iterate over all the nodes after nodeToDelete. Let curr be the current node. We will copy the value of the next to the current node. Thus the value of the node to be deleted will be replaced with the value of the next node. For example the given list 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 and 3 be the node to be deleted:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
|
curr
1 -> 2 -> 4 -> 4 -> 5 -> 6 -> 7
|
curr
1 -> 2 -> 4 -> 5 -> 5 -> 6 -> 7
|
curr
1 -> 2 -> 4 -> 5 -> 6 -> 6 -> 7
|
curr
When we are the second last node (i.e. curr.next.next is null), we will copy the value of the last node and then we will delete the last node by setting curr.next = null.
1 -> 2 -> 4 -> 5 -> 6 -> 7 -> 7 (copy)
|
curr
1 -> 2 -> 4 -> 5 -> 6 -> 7 (delete last node)
|
curr
class ListNode {
constructor(val, next) {
this.val = val || 0
this.next = next || null
}
}
/**
* @param {ListNode} nodeToDelete
* @return {void} Do not return anything,
* modify node in-place instead.
*/
function deleteNode(nodeToDelete) {
let curr = nodeToDelete
while(true) {
// copy value of next node
curr.val = curr.next.val
// curr is the second last node
// curr.next is the last node
// delete it, and break loop
if (curr.next.next === null) {
curr.next = null
break
}
curr = curr.next
}
}n = length linked list
Time complexity- O(n)
Written by S. Kumar on May 5th, 2021
5. Merge two sorted lists.
This interview question focuses on the developer's ability to use JavaScript iteration.
You are given two sorted singly-linked lists. Your task is to merge both linked lists and return it to a new linked list.
/*Example*/
Given:- l1 = [1, 3, 4] l2 = [2, 5, 6]
Expected output:- [1, 2, 3, 4, 5, 6]Solution:
We will iterate over all the nodes of the lists. We will have two pointers curr1 and curr2 pointing to the current nodes we are processing for both the lists. We will compare the values of the current node and will append a new node with the smaller value. For example, if curr1 has a smaller value than curr2, we will create a new node with the value curr1.val and advance curr1 by using curr1 = curr1.next and vice-versa for curr2.
There may be cases where one list is shorter than the other. We will, first, set default values of variables a and b to Infinity. Then if curr1 is not null, we will update a, and if curr2 is not null we will update b.
To store the new list, we will use a dummy node with the value NaN (the value does not matter, it can be any). A dummy node is a placeholder node that is used to initialize a new linked list when we don't have the head node. In our case, any of the lists can have a smaller head node thus making the head of the new list. For example:
After initializing, the new list dummy is:
NaN
after the first iteration
NaN -> 1
after the second iteration
NaN -> 1 -> 2
after the third iteration
NaN -> 1 -> 2 -> 3
after the third iteration
NaN -> 1 -> 2 -> 3 -> 4
..
..
after the final iteration
NaN -> 1 -> 2 -> 3 -> 4 -> 5 -> 6
So our resulting list starts from the second node of the list starting with dummy i.e. dummy.next.
class ListNode {
constructor(val, next) {
this.val = val || 0
this.next = next || null
}
}
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
function mergeLists(l1, l2) {
let curr1 = l1
let curr2 = l2
const dummy = new ListNode(NaN)
let dummyCurr = dummy
while(curr1 !== null || curr2 !== null) {
let a = Infinity
let b = Infinity
if (curr1 !== null) a = curr1.val
if (curr2 !== null) b = curr2.val
if (a < b) {
let newNode = new ListNode(a)
dummyCurr.next = newNode
dummyCurr = dummyCurr.next
curr1 = curr1.next
} else {
let newNode = new ListNode(b)
dummyCurr.next = newNode
dummyCurr = dummyCurr.next
curr2 = curr2.next
}
}
return dummy.next
}m = length first linked list
n = length second linked list
Time complexity- O(m + n)
Space complexity- O(1)
Written by S. Kumar on May 5th, 2021
6. Can you remove nodes between indices from list1 and replace them with list2 nodes?
This question concentrates on the developer's knowledge of JavaScript indices and lists.
You are given two singly-linked lists list1 and list2. You are also given two 0-based indices start and end. The two given indices are corresponding to list1. Your task is to remove the nodes between indices start and end of list1 both inclusive and place list2 in place of the deleted nodes.
/*Example*?
Given:
list1 = 11 -> 12 -> 13 -> 14 -> 15 -> 16
list2 = 21 -> 22
start = 2 end = 4
Expected output: 11 -> 12 -> 21 -> 22 -> 16
Explanation:
list1 = 11 -> 12 -> 13 -> 14 -> 15 -> 16
indices = 0 1 2 3 4 5
| |
start end (these nodes are deleted)
11 -> 12 13 -> 14 -> 15 16
\ /
---> 21 -> 22 --->
Constraint:
â— 3 <= list1.length
â— 1 <= a <= b < list.length - 1
â— 1 <= list2.lengthSolution:
First, we find the start and the end nodes of list2. These are represented by list2FirstNode and list2LastNode. After that, we find the pointers to nodes at index start - 1 and end + 1. For the given example, to find the node at index start - 1,
11 -> 12 -> 13 -> 14 -> 15 -> 16
|
curr
i = 0
11 -> 12 -> 13 -> 14 -> 15 -> 16
|
curr
i = 1 (we stop here as i == start - 1)
After we get the node at index start - 1, we first store the reference to the next node (node at index start) in temp and then assign it’s next to list2FirstNode. Then we again iterate over list1 to get the reference to the node at index end + 1 and assign the next of list2LastNode to this node.
class ListNode {
constructor(val, next) {
this.val = val || 0
this.next = next || null
}
}
/**
* @param {ListNode} list1
* @param {number} start
* @param {number} end
* @param {ListNode} list2
* @return {ListNode}
*/
function mergeInBetween(list1, start, end, list2) {
let list2FirstNode = list2
let list2LastNode = list2
while (list2LastNode.next !== null) {
list2LastNode = list2LastNode.next
}
let i = 0
let curr = list1
while(i < start - 1) {
curr = curr.next
i++
}
let temp = curr.next
curr.next = list2FirstNode
// curr holds the node at index start
curr = temp
i++
while(i <= end) {
curr = curr.next
i++
}
list2LastNode.next = curr
return list1
}n = length second linked list
Time complexity- O(end + m)
Space complexity- O(1)
Written by S. Kumar on May 5th, 2021
7. Create a deep copy of the special-linked list.
This interview question shows the developer's ability to work with JavaScript loops.
You are given the head node of a linked list. The linked list is special. In addition to the value of the node and next pointer of the node, the nodes contain additional pointer random. This random pointer points to any random point of the list. It may be null also.
Your task is to create a deep copy of the list. There must be new nodes created corresponding to each node in the given list. Their next and random pointers must point to nodes with the same value as in the given list. None of the pointers in the new list should point to nodes in the given list. Return the head of the new list created.
/*Example*/
Given list
1 -> 2 -> 3 -> 4 -> 5 -> 6
| | | | | |
--->-|-->-- | | |
--<----<--|--<-- |
--->--->---
That is:
1.random = 3
2.random = null
3.random = null
4.random = 6
5.random = 2
6.random = null
Expected output:
1 -> 2 -> 3 -> 4 -> 5 -> 6
| | | | | |
--->-|-->-- | | |
--<----<--|--<-- |
--->--->---
(We need the exact same list but deep copied.)Solution:
First, we will create new nodes with values in the original list. For every node in the original list, we will create a new node with the same value and store it in a map reference. The keys of references will be the references of nodes in the original list and the values will be references to corresponding new nodes created. For example,
Let’s say original_{val} be the node in the original list with value val, and new_{val} be the corresponding new node created. After iterating over all the nodes, the map references look like:
{
original_1 -> new_1
original_2 -> new_2
original_3 -> new_3
original_4 -> new_4
original_5 -> new_5
original_6 -> new_6
}
After this, we will again iterate over the original list and will assign corresponding next and random pointers to the new nodes. For one iteration, say curr = original_1, the value of variables in the loop are:
curr = original_1
curr.next = original_2
curr.random = original_3
---------------------------
newNode = new_1
newNode.next = new_2
newNode.random = new_3
class ListNode {
constructor(val, next, random) {
this.val = val || 0
this.next = next || null
this.random = random || null
}
}
/**
* @param {ListNode} head
* @return {ListNode}
*/
function copySpecialList(head) {
if (head === null) return null
let curr = head
let references = new Map()
while(curr !== null) {
const newNode = new ListNode(curr.val)
references.set(curr, newNode)
curr = curr.next
}
curr = head
while(curr !== null) {
const newNode = references.get(curr)
newNode.next = references.get(curr.next) || null
newNode.random = references.get(curr.random) || null
curr = curr.next
}
return references.get(head)
}n = length the linked list
Time complexity- O(n)
Space complexity- O(n)
Written by S. Kumar on May 5th, 2021
8. Does the list contain a cycle?
This question focuses on JavaScript pointers.
You are given the head of a singly linked list. Your task is to check if the list contains a cycle or not.
/*Example*/
Given list:- 1 -> 2 -> 3 -> 4 -> 5
Expected output:- false
Given list:- 1 -> 2 -> 3 -> 4 -> 5
| |
---<---<---<----
Expected output:- trueSolution:
This is a very famous problem with a famous solution. The solution is known as fast-slow pointers. We will have two pointers: slow and fast. In every iteration, we will advance slowly by one step while we advance fast by two steps.
â— If there is no cycle, the loop will break, as either fast.next or fast.next.next will be null and we will return false.
â— If there is a cycle, after the last node, the fast pointer will be in the cycle. It will always be in the cycle. Since the difference of steps between the fast and slow pointer that they take is one only, there will be a point when they both point to the same node. When they do so, we will return true.
For example 2, given list:- 1 -> 2 -> 3 -> 4 -> 5 (5.next = 2 i.e. there is a cycle but we are not showing it here for simplicity)
-> slow
|
1 -> 2 -> 3 -> 4 -> 5
|
fast
-----------------------------------------------
slow
|
1 -> 2 -> 3 -> 4 -> 5
|
fast
-----------------------------------------------
slow
|
1 -> 2 -> 3 -> 4 -> 5
|
fast
-----------------------------------------------
slow
|
1 -> 2 -> 3 -> 4 -> 5
|
fast (fast pointer is in cycle now, 5.next.next = 2.next = 3)
-----------------------------------------------
slow
|
1 -> 2 -> 3 -> 4 -> 5
|
fast (both point to the same node, return true)
class ListNode {
constructor(val, next) {
this.val = val || 0
this.next = next || null
}
}
/**
* @param {ListNode} head
* @return {boolean}
*/
function hasCycle(head) {
if (head === null) return false
let slow = head
let fast = head
while(fast.next !== null && fast.next.next !== null) {
slow = slow.next
fast = fast.next.next
if (slow === fast) return true
}
return false
}n = length the linked list
Time complexity- O(n)
Space complexity- O(1)
Written by S. Kumar on May 5th, 2021
9. How do you rotate the list?
This interview question shows the developer's ability to work with JavaScript list length.
You are given the head node of a singly-linked list. You are also given an integer k. Your task is to rotate the list right by k places.
/*Example*/
Given list:- 1 -> 2 -> 3 -> 4 -> 5 k = 2
Expected output:- 4 -> 5 -> 1 -> 2 -> 3
Explanation:
After 1st rotation:- 5 -> 1 -> 2 -> 3 -> 4
After 2nd rotation:- 4 -> 5 -> 1 -> 2 -> 3Solution:
We first find the length of the list, let it be len. The value of k can be anything, even 0 or greater than len. The list after k rotations and the list after k + len rotations will be the same. So we normalize the value k. We take a modulo of k with len. Now the value of lies between 0 and len - 1. If k is 0, then no rotation is required. So we return the head without modifying anything.
Otherwise, we iterate over the list. As observed from the example, if the rotations required are 2, 2 nodes from the end of the list will become forward. The first (len - k) nodes will be the tail. The (len - k)th node (1-indexed) will be the last node in the list after k rotations. Thus we iterate over the list and find the (len - k)th node.
The new head of the new list will be (len - k + 1)st i.e. next of (len - k)th. Then iterate up to the last node of the list. After finding the last node, we set it’s next to the original head.
For the given example, len = 5, k = 2
newHead
|
1 -> 2 -> 3 -> 4 -> 5
|
(len - k)th node (this node will be the last node in new list, we set it’s next to null after finding it)
class ListNode {
constructor(val, next) {
this.val = val || 0
this.next = next || null
}
}
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
function roateList(head, k) {
if (head === null) return null
let len = 0
let curr = head
while(curr !== null) {
curr = curr.next
len++
}
k = k % len
if (k === 0) return head
let i = 1
curr = head
while(i < (len - k)) {
curr = curr.next
i++
}
let newHead = curr.next
curr.next = null
curr = newHead
while(curr.next !== null) {
curr = curr.next
}
// curr is the last node in the original list
curr.next = head
return newHead
}n = length the linked list
Time complexity- O(n)
Space complexity- O(1)
Written by S. Kumar on May 5th, 2021