Finding the Middle of a Linked List

A common interview problem is, given a linked list, return the node that's in the middle. If there are two "middle nodes", return the second one. (You can find this problem on Leetcode here.)

One approach to this problem involve iterating through the linked list, putting each node value in a new array, and then finding the middle element of the array. This approach does have a time complexity of O(n), and a space complexity of O(n), since all of the nodes are put into a new array.

How would you solve this with a space complexity of O(1)? In this post, I'll walk through a straightforward solution to this common problem. First, I'll explain how the solution works in diagrams. Then, I'll walk through how to code it out using JavaScript.

Two Pointers: Visualization Using Diagrams

The idea behind this approach is to have two different pointers--one that is "fast" and one that is "slow". The slow pointer moves one node at a time. The fast pointer moves two nodes at a time. When the fast pointer gets to the end of the list, that's when the slow pointer will be at the middle of the list.

I originally had difficulty visualizing this, but once I drew it out with diagrams, it made a lot more sense.

Let's say you're given a linked list. The first box represents the head. You'll have two pointers, slow and fast, which both start at the head.

Now, after one turn, the slow pointer will move one node, and the fast pointer will move two.

The fast pointer is still not at the end of the list (which you know because node.next is not null). So, there needs to be another turn. The slow pointer again moves one node, and the faster pointer moves two.

Now, the fast pointer is at the end of the linked list, and the slow pointer is at the middle of the linked list.

Two Pointers: The Code

To write this out, we have to first initialize two variables: fast and slow. In the function, you're given the head of the linked list, so you should set both fast and slow equal to the head. (You also can assume the linked list nodes have certain properties, such that node.val is the value of the node, node.next is the next node, and node.next.next is two nodes down.)

function middleNode(head) {
  let fast = head;
  let slow = head;

  //...
}

Now, we want to create a loop for the fast and slow variables to keep changing. We want them to keep changing as long as 'fast' is not null, and as long as the next node is not null. Once fast is null and/or the next node is null, you know fast is at the end of the list, and so slow is on the middle node. Inside the while loop is where we change slow and fast. Slow will be set to equal slow.next, and fast will equal fast.next.next.

function middleNode(head) {
  let fast = head;
  let slow = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  //...
}

Once the while loop ends, you know fast made it to the end of the linked list, which means slow is at the middle of the list. Now, we can simply return the node that slow is at, and that's the end of the function.

function middleNode(head) {
  let fast = head;
  let slow = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

Let me know in the comments if you have any questions or other approaches to this problem!

Comments

[Duy K. Bui]

The problem is simple but I love how you explain the solution. Very easy to understand for beginners. Keep up the good work!

[Hal Friday]

this solution is so smart. i went about it a much more verbose way...counted the number of nodes, saved the length/2, then stepped through to the middlemost point. kind of a fun one to do