Given a singly linked list, find the middle of the linked list. For example, if the given linked list is 1->2->3->4->5 then the output should be 3.
If there are even nodes, then there would be two middle nodes, we need to print the second middle element. For example, if given linked list is 1->2->3->4->5->6 then the output should be 4.
Write a function which will accept a pointer to the head of the linked list and returns a pointer to the middle node of the list.If the list given is
2 -> 3 -> 5 -> 1 -> 4 -> 8 -> 10Then the function should return a pointer to Node with value 1. If the list has even number of elements
2 -> 3 -> 5 -> 1 -> 4 -> 8Then you may return a pointer to either 5 or 1 [Since there is no clear middle node].
Another way to ask this question is “Given a linked list, write code to split is in two halves“. In this case also you have to write code to reach to the middle of the list and then update the pointers of the middle node .
Solution:
Simple way [Using 2 loops]
Using only one loop.
Refer to this post for the Idea. The idea is to take 2 pointer and move one pointer forward at twice the speed of 2nd pointer. When the first reach end of the list, second pointer will be at the middle.
Take 2 pointers, both pointing to the head of the list initially. While 1st pointer is not NULL Move 1st pointer to next of next Node. Move 2nd pointer to next Node. return 2nd pointerThough this method is not more efficient than the previous one [both in terms of time & memory usage]. But sometimes interviewer asks that he want to use only one loop.
/** * Function to return the middle element in the list. * Returns NULL, if the list is empty. * Returns the 1st of the 2 middle elements if list has even number of node. **/ Node* getMiddle[Node *head] { if[head == NULL || head->next == NULL] return head; Node *ptr1 = head; // Will move 1 node frwd Node *ptr2 = head; // Will move 2 nodes frwd // we don't need to check for ptr1. because ptr2 ahead of ptr1 while[ptr2->next!= NULL && ptr2->next->next != NULL] { ptr2 = ptr2->next->next; ptr1 = ptr1->next; } return ptr1; }semma
here is my solution in c++, python and java
//code2begin.blogspot.com/2017/03/finding-middle-node-in-linked-list.html
Nice article well explained . there is good linkedlist examples collection
thank you so much very helpful
Your email address will not be published. Required fields are marked *
Comment
Name *
Email *
Website
Save my name, email, and website in this browser for the next time I comment.
Solution Steps
Algorithm:
In order to find middle element of linked list in one pass, you need to maintain two pointers, one increment at each node while other increments after two nodes at a time. By having this arrangement, when first pointer reaches end, second pointer will point to middle element of linked list.
Algorithm
In this tutorial, we're going to explain how to find the middle element of a linked list in Java.
We'll introduce the main problems in the next sections, and we'll show different approaches to solving them.
#include #include /* Link list node */ struct Node { int data; struct Node* next; }; /* Function to get the middle of the linked list*/ void printMiddle[struct Node *head] { struct Node *slow_ptr = head; struct Node *fast_ptr = head; if [head!=NULL] { while [fast_ptr != NULL && fast_ptr->next != NULL] { fast_ptr = fast_ptr->next->next; slow_ptr = slow_ptr->next; } printf["The middle element is [%d] ", slow_ptr->data]; } } void push[struct Node** head_ref,int new_data] { /* allocate node */ struct Node* new_node = [struct Node*]malloc[sizeof[struct Node]]; /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = [*head_ref]; /* move the head to point to the new node */ [*head_ref] = new_node; } // A utility function to print a given linked list void printList[struct Node *ptr] { while [ptr != NULL] { printf["%d->", ptr->data]; ptr = ptr->next; } printf["NULL "]; } /* Drier program to test above function*/ int main[] { /* Start with the empty list */ struct Node* head = NULL; int i; for [i=5; i>0; i--] { push[&head, i]; printList[head]; printMiddle[head]; } return 0; } |