Middle node of linked list : Hare and Tortoise algorithm

Middle node of linked list

In this post, we will learn a very important concept about linked lists. This concept is called as Hare and Tortoise algorithm. Problem statement is to find middle node of linked list. For example,

1->2->3->4->5->null
 Middle of linked list is 3

1->2->3->4->5->6->null
Middle of linked lists is 4

Brute force approach

Brute force solution is : scan the whole linked list and get number of nodes (n) in it. Then again, traverse n/2 nodes starting from head and that will be middle of linked list. Well, this is simple to implement but it cost 3/2 times length of linked list. In amortized time complexity analysis, worst case time complexity of this method will be O(n)

1. Scan whole linked list and count number of nodes
2. Divide total number of nodes by 2
3. Now scan list for number of nodes found in step 2

Middle node of linked  list : Hare and Tortoise algorithm

Second method is Hare and Tortoise algorithm. In Hare and Tortoise algorithm, we maintain two pointers: fast and slow. Fast pointer moves two nodes of linked list, while slow pointer moves only one node at a time. Now, since fast pointer is moving twice as fast as slow, it will reach end of list twice fast than slow pointer. What does that imply? Yes, it implies that slow pointer will be at middle of linked list when fast pointer reaches end.

1. Initialize fast and slow pointers as head
2. While fast pointer does not reach end
   2.a move fast pointer two nodes at a time.
   2.b move slow pointer one node.
3. If fast pointer reached last node, return slow pointer.
#include <stdio.h>
#include <stdlib.h>
 
typedef struct Node {
  int data;
  struct Node * next;
} Node;
 
Node * createNode(int val){
  Node * temp = (Node *)malloc(sizeof(Node));
  if(temp){
    temp->data = val;
    temp->next = NULL;
  }
  return temp;
}
/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
	Node * newNode  = createNode(data);
	newNode->next = *headRef;
	*headRef  = newNode;
}
void printList(Node *head){
	while(head){
		printf("%d->", head->data);
		head = head->next;
	}
	printf("Null");
}
 
/* 
   Function to find middle node using hare and tortoise algorithm
 */
Node * findMiddleNode(Node * head){
	//Wrong list, there is no middle node.
	if(!head) return NULL;
 
	Node *fast = head->next;
	Node *slow = head;
 
	while(fast){
		fast = fast->next;
		//check if fast is not null yet
		if(fast)
			fast = fast->next;
		slow = slow->next;
	}
	return slow;
}
 
int main(void) {
 
	Node * head = NULL;
	push(&head, 3);
	push(&head, 4);

	Node * nodeToDelete = head;

	push(&head, 5);
	push(&head, 6);
	push(&head, 7);
	push(&head, 8);
	push(&head, 9);

	printf("\nOriginal list :");
	printList(head);

	Node *mid = findMiddleNode(head);
  	printf("\nMiddle node : %d",  mid ? mid->data : 0);
	return 0;
}

Time complexity of Hare and Tortoise algorithm is still O(n). However, while loop in step 2 runs only of n/2 times and we are done! There is an argument, that we are actually scanning the list 3/2 times, fast scanning it completely while slower one by half. Still, since we are scanning three nodes at once, loop finishes in n/2 iterations.

Another optimization on second method to find middle node of linked list is : instead of moving slow pointer, we keep a counter. We start with assumption that head node is middle node. We scan the linked list and increment counter when new node is scanned. If counter value is odd, move mid node (initialized as head to start with) to mid’s next. When scan of entire list is done, mid will be middle node of linked list.

1. Initialize mid to head, counter = 0
2. While there are nodes in list
   2.1 Increment counter
   2.2 if counter is odd, move mid pointer to it's next
3. return mid
#include <stdio.h>
#include <stdlib.h>
 
typedef struct Node {
  int data;
  struct Node * next;
} Node;
 
Node * createNode(int val){
  Node * temp = (Node *)malloc(sizeof(Node));
  if(temp){
    temp->data = val;
    temp->next = NULL;
  }
  return temp;
}

/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
	Node * newNode  = createNode(data);
	newNode->next = *headRef;
	*headRef  = newNode;
}

void printList(Node *head){
	while(head){
	    printf("%d->", head->data);
	    head = head->next;
	}
	printf("Null");
}
 
/* Function to find middle node using modified hare and tortoise algo */
Node * findMiddleNode(Node * head){
	//Wrong list, there is no middle node.
	if(!head) return NULL;
 
	Node *fast = head;
	Node *mid = head;
	int counter = 0;
 
	while(fast){
	    //if you and an odd number, it will return 1, else 0
	    if(counter & 1) {
		//If counter is odd, move mid to mid's next
		mid = mid->next;
	    }
	    counter++;
	    fast = fast->next;
	}
	return mid;
}
 
int main(void) {
 
	Node * head = NULL;
	push(&head, 3);
	push(&head, 4);

	Node * nodeToDelete = head;

	push(&head, 5);
	push(&head, 6);
	push(&head, 7);
	push(&head, 8);
	push(&head, 9);

	printf("\nOriginal list :");
	printList(head);

	Node *mid = findMiddleNode(head);
        printf("\nMiddle node : %d",  mid ? mid->data : 0);
	
       return 0;
}

Complexity of optimized version is also O(n), however, there are n iterations of while loop.
Time complexity of all implementation to find middle node of list is O(n). Difference is actual iteration of loop vary, and on that we can claim that second method is better than other two.

Note of caution
Whenever you are asked to find middle of anything, keep in mind to verify your solution for even and odd number input and ask interviewer with example, if the solution provided are acceptable in both cases.

Finding middle of linked list is quite useful when implementing merge sort on linked list.

For more problems on linked list, please refer : Linked list problems

Please share if there is something is wrong or missing. If you are interested in contributing to website or have an interview to share, please contact us.