How to Answer: Return the middle node of a given linked list.
Advice and answer examples written specifically for a Javascript Beginner Level Linked Lists job interview.
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