Middle of a Singly Linked List

In this article, we are going to discuss a very interesting topic, “how to get middle of a singly linked list”. Before that, we will see the different algorithms to get the middle of any linear data structure. There are two ways to get the middle of any linear data structure.

(Size of data structure) / 2  : This is the most common way to get the middle of any index based linear data structures. To get the middle element, divide the size of collection by 2 to get the middle element. If size of collection is even number , we can declare any two middle index as middle of the collection.Ex: if size=6 then we can say index=3 or index =2 can be the middle index. If size of collection is odd number, we will have only one middle index. Ex: if size=5 then middle index=2.

Algorithm:

  1. Suppose size of collection is N and index start from 0 to N-1.
  2. Divide size by 2 to get the integer index value .
  3. get the element by index.

This approach is useful when we have indexed linear data structure, because we can get the elements by index. But for non-indexed linear data structures, we need to traverse through the elements. Below is the optimal solution to get the middle of non-indexed linear data structure.

Pointer Movement: To understand this approach, assume we have 10 feet long road. Two men started walking from one end. Now, condition is, first man can take 2 feet long step but second man can take 1 foot long step. Both men will get the similar opportunity to step ahead one by one. Obviously, first man will reach early  at other end of the road. Now, when first man will reach at other end of the road, what will be the position of second man ? Since step size of first man is double as compare to the second man, position of second man will be middle of the road when first man reaches at other end of the road.

Similar concept applies to get the middle of any linear data structure .

If fast moving pointer reaches at the end of the linear data structure, that time,  position of slow moving pointer will be at middle. Speed of fast pointer = 2* (Speed of slow pointer).

 

Refer the below algorithm and execution process to get middle of singly linked list.

Algorithm:

  1. Declare two node variables , fastPointer and slowPointer.
  2. Initialize fastPointer =root->next Node
  3. Initialize slowPointer=root
  4. Move fast pointer by 2 and slow pointer by 1 till fast pointer is not equal to null.To do so, repeat the steps 5 and 6  till fastPointer !=null
  5. fastPointer = fastPointer -> next Node
  6. if  fastPointer !=null  , move slow pointer and fast pointer one step ahead
  7. Finally, when fast pointer reaches at end of the linked list i.e fastPointer == null , slow pointer will be at middle of the linked list.

 

Execution Process : 

See the below Java code implementation to get middle of a singly linked list.

 

Output:

Original List: [Item [itemId=101, itemName=IPhone-5S, price=200.0],Item [itemId=102, itemName=IPhone-6S, price=500.0],Item [itemId=103, itemName=IPhone-XX, price=1000.0],Item [itemId=104, itemName=IPad, price=500.0],Item [itemId=105, itemName=IPod, price=500.0]]

Middle Item : Item [itemId=103, itemName=IPhone-XX, price=1000.0]

**************************************************************************************

 

There are many uses of getting the middle element of linear data structures like Binary search and Merge sort. In next post, we will discuss about sorting of Singly Linked list.

 

Hope you like this post. Please leave your comments/suggestions.

You may like –

 

Top