Linked Lists — slow and fast

Today we are going to be solving a linked list problem. Now if you are unfamiliar with linked lists, let’s get you up to speed.

According to Wikipedia, “In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.”

So we can imagine a linked list as a data structure where one node points to the next node and we can only move through this sequence one by one. Accessing each node’s “next” attribute will move us to the next node. As well, each node has a “value” attribute. If you’re still confused let’s see one in action.

Today we are going to be solving Middle of the Linked List:

Most linked list problems can be solved using a pointer system. In this example we will use two pointers to find the middle of a linked list.

A pointer will be a variable that references a specific node. In our case we want to have ‘slow’ pointer that will move one node at a time and we will have a ‘fast’ pointer that will move two nodes at a time. We will keep moving these pointers until the ‘fast’ pointer has reached the very end of our linked list.

We will start both pointers at the beginning of the list, which is the head.

We keep moving our pointers until the fast node reaches null.

We stop at this point because our fast.next is equal to null. We cannot advance our fast pointer anymore. Since our fast pointer was moving 2x as fast as our slow it means our slow pointer is sitting on the exact middle point of the linked list. We simply return our slow pointer as the answer.

Here is the code!