Linked list stack picture8/3/2023 ![]() ![]() Both slow and fast will be pointing to the head of the list. Now, as we have the slow pointer pointing to the middle of the list, we will add the new node just after the slow pointer.When the fast pointer reaches the end of the linked list, the slow pointer will be pointing to the middle of the linked list.The fast pointer will jump two places, whereas the slow pointer will jump only one place. Then, we will start moving both of the pointers.Initially, both the pointers, slow and fast, will point to the head of the linked list.Let us see what the slow and fast pointer technique is: Approach to to insert a node at the middle of linked list(Slow and Fast Pointer) The slow and fast pointer method has been explained in detail in the approach section and the dry run. This method is called the tortoise and hare method or the slow and fast pointer method. ![]() Note: The reason why slow will be pointing to the middle of the linked list when fast reaches the end is that, as our slow pointer is travelling with half of the speed of the fast pointer, so when fast pointer will reach the end of the linked list, till that time slow pointer will have travelled only half the distance as travelled by fast pointer and hence it will be at the middle of the linked list.ĭo you know what the above-explained method is called? With the help of this technique, we can reach the middle node of a linked list in a single pass.If we notice carefully, by doing the above step when the fast will reach the end of the list, the slow will be pointing to the middle of the list.What will happen if we make the slow jump one place and the fast jump two places?.What if we start by taking two pointers, say slow and fast, and make both points to the head initially. We can optimize the algorithm to insert an element in the middle of a linked list, as in this technique, we are doing two traversals of the given list. If we think carefully, the answer is yes.This approach is okay, but can we further optimize it? In this way, the new node gets added into the middle of the list.Traverse k nodes and add the new node just after the k th node.Here, k denotes the middle point of the list.k will (len/2) if len is even, else it will (len+1)/2. With the help of list traversal, find the length of the linked list.So, if the length is even, we will add the new node after (length/2) th node of the linked list, else we will add the new node after ((length+1)/2) th node of the linked list.Īlgorithm to insert a node at the middle of linked list.As we know if the length is even, then the middle node is (length/2) th node, else the middle is ((length+1)/2) th node. ![]()
0 Comments
Leave a Reply.AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |