Linked List is dynamic data structure that is used to store information. Unlike arrays linked lists are not stored in contagious memory locations rather the are stored at any empty place in memory and the address of the next node is stored in the link field. Hence we don't have direct access to the Linked List elements as we do in arrays.
In order to find the middle node of the Linked List there are 2 methods
Method 1 :
Traverse the Linked list count the number of nodes and then move a pointer to that node by using a counter. This method although useful requires us to traverse the List 2 times.
Method 2 :
Use 2 pointers (say) fast and slow starting from the head node increment the fast pointer by 2 and increment the slow pointer by 1. In this way when the fast pointer reaches the end the slow pointer will point to the middle element.
To know more about Linked List and its implementation click Here.
The following is the implementation of the Method 2.
You might also be interested in
Singly Linked List
Double Linked List
Linked List in Python
Stack Implementation using Linked List
Queue Implementation using Linked List
Infix to Prefix Conversion
Infix to Postfix Conversion
Binary Search Tree
In order to find the middle node of the Linked List there are 2 methods
Method 1 :
Traverse the Linked list count the number of nodes and then move a pointer to that node by using a counter. This method although useful requires us to traverse the List 2 times.
Method 2 :
Use 2 pointers (say) fast and slow starting from the head node increment the fast pointer by 2 and increment the slow pointer by 1. In this way when the fast pointer reaches the end the slow pointer will point to the middle element.
To know more about Linked List and its implementation click Here.
The following is the implementation of the Method 2.
C++ Program
Sample input and output to check the program
You might also be interested in
Singly Linked List
Double Linked List
Linked List in Python
Stack Implementation using Linked List
Queue Implementation using Linked List
Infix to Prefix Conversion
Infix to Postfix Conversion
Binary Search Tree
Comments
Post a Comment