easy

Middle of the Linked List

To find the middle node of a linked list, we can use the two-pointer technique, also known as the slow and fast pointers. The slow pointer moves one node at a time while the fast pointer moves two nodes at a time. When the fast pointer reaches the end of the list, the slow pointer will be pointing to the middle node.

Here is one way to implement the find middle node function in JavaScript:

function findMiddleNode(head) {
  let slow = head;
  let fast = head;
 
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }
 
  return slow;
}

In this implementation, we use two pointers: slow and fast. Both pointers are initially set to the head of the list. We then iterate through the list using a while loop, updating the pointers as follows:

• Move the slow pointer to the next node.
• Move the fast pointer to the next node twice as fast.
• At the end of the loop, the slow pointer will be pointing to the middle node of the list.

The time complexity of this implementation is O(n), where n is the number of nodes in the linked list, since we need to iterate through all the nodes once. The space complexity is O(1), since we are only using a constant amount of extra memory to store the pointers.