Hadron DaVinci

Find Value at Middle Node in Single Linked List

08 Aug 2020 - Hadron DaVinci

Problem

Find Middle Node of Single Linked List:
1 => 2 => 3 => 4 => 5 => 6

Discussion

Truths:

1. A linked list is not the same data structure as an array or list.
   • so we can’t just jump to the middle index.
   • we can only get there by accessing a node which points to it
2. A single linked list means that one can traverse the linked list only forwards.
   
   
   

Solutions

Method1 (Brute Force):

step1:

Obtain the length of linked list by iterating from left side to right side once
while counting the number of nodes.

• Let length_linked_list = number of nodes

step2:

Find the mid point.

• Let mid_point = length_linked_list/2

step3:

Iterate through the list until we get to the middle

• Let current_node_index = 0, as code iterates, do current_node_index += 1
  Stop when current_node_index >= mid_point

Method2 (Fast and Slow Iterator):

Create a fast and slow iterator.

• The fast iterator skips 2 nodes/iteration and the slow iterator skips 1 node/iteration.
  
• Both start on the left side.
  
• Since the fast iterator is moving twice as fast, when it stops at (or passes) the end,
  the slow iterator will be in the middle!
  

This technique is pretty cool b/c it uses related rates to our advantage