How to find middle node of a Singly linkedlist

Introduction

A linkedlist is a linear data structure, but unlike an array we can’t access elements in a linkedlist using index. Hence it becomes a little difficult to find middle of a linkedlist.

In this blog we will see how to find middle of a linkedlist in two ways:

• Naive approach
• Using hare and tortoise technique

Finding middle node using naive approach

In the naive approach:

• First we find the length of linkedlist by iterating over it.
• Then we iterate again till half the length we found in first step.

Lets see the code for this approach:

func findLengthOfLinkedlist(head *Node) int {
    var length int
    // iterate till end of linkedlist
    for node := head; node!=nil; node = node.next {
        // increase length by one for each iteration
        length += 1
    }
    return length
}

func findMiddleNode(head *Node) *Node {
    len := findLengthOfLinkedlist(head)
    // if length is less than or equal to one then there's no mid
    if len <= 1 {
        return head
    }
    // initialize mid to be half of length
    mid := len/2
    // initialise node as head
    node := head
    // iterate till mid
    for i := 0; i < mid; i++ {
        // keep moving the node ahead by one
        node = node.next
    }
    // return the node
    return node
}

Finding middle node using hare and tortoise technique

In hare and tortoise technique:

• We take two pointers hare and tortoise and initialize them as the head of linkedlist.
• Now iterate over the linkedlist till hare reaches the end of linkedlist.
• While iterating move tortoise one node and hare two nodes ahead in every iteration.
• By the time hare reaches the end of linkedlist, the tortoise would have only reached the middle node of linkedlist.
• Since tortoise will be at the middle node we return the tortoise at the end.

Lets see how to implement this:

func FindMiddleOfLinkedlist(head *Node) *Node {
    // if head is nil return the head as linkedlist is empty
    if head == nil {
        return head
    }
    // initialize hare and tortoise as head of linkedlist
    hare, tortoise := head
    // iterate over linkedlist till hare reaches end
    for hare != nil && hare.next != nil {
        // move tortoise by one and hare two nodes ahead
        hare, tortoise = hare.next.next, tortoise.next
    }
    // return tortise
    return tortoise
}

Let’s take a look at an example for dry run of above technique:

• At the inital position both hare and tortoise are pointing to head of linkedlist.

  

• After first iteration:
  • tortoise is at node-2
  • hare is at node-3

  

• After second iteration:
  • tortoise is at node-3
  • hare is at node-5

  

• After third iteration:
  • tortoise is at node-4
  • hare is at node-7(tail of linkedlist)

  

• The loop will break as hare.next will be nil.

Closing words

Hope you liked the blogs in this linkedlist series. This is the last blog for this series. In this series we saw:

• Linkedlist basics
• Implementing Singly linkeldist
• Implementing Doubly linkeldist
• Implementing Circular linkeldist
• Detecting cycle in linkedlist
• Finding starting node of cycle in linkedlist

I hope you enjoyed reading this blog and it added some value.