How will you find the middle element of a singly linked list without i

1.	How will you find the middle element of a singly linked list without iterating the list more than once?
Answer» To SOLVE this problem, we can use the two-pointer method. You have two pointers, one fast and one slow, in the two-pointer approach. The fast pointer travels two nodes per step, while the slow pointer only moves one. The slow pointer will point to the middle node of the LINKED list when the fast pointer points to the last node, i.e. when the next node is null. Node* getMiddle(Node head){ STRUCT Node slow = head; struct Node *fast = head; if (head) { while (fast != NULL && fast-&GT;next != NULL) { fast = fast->next->next; slow = slow->next; } } return slow;} Time Complexity: O(n) Space Complexity: O(1)

How will you find the middle element of a singly linked list without iterating the list more than once?

Answer»

To SOLVE this problem, we can use the two-pointer method. You have two pointers, one fast and one slow, in the two-pointer approach. The fast pointer travels two nodes per step, while the slow pointer only moves one. The slow pointer will point to the middle node of the LINKED list when the fast pointer points to the last node, i.e. when the next node is null.

Node* getMiddle(Node *head){ STRUCT Node *slow = head; struct Node *fast = head; if (head) { while (fast != NULL && fast-&GT;next != NULL) { fast = fast->next->next; slow = slow->next; } } return slow;}

Time Complexity: O(n)
Space Complexity: O(1)

Discussion

No Comment Found

Related InterviewSolutions

A given linked list is sorted based on absolute values. Write a function to sort the list based on actual values in O(n) time.
Given a linked list and a number n, you have to find the sum of the last n nodes of the linked list in a single traversal. Explain your approach in brief.
How will you modify a linked list of integers so that all even numbers appear before all odd numbers in the modified linked list? Also, keep the even and odd numbers in the same order.
A linked list of coordinates is given, with neighboring points forming either a vertical or horizontal line. Remove points in between the starting and ending points of the horizontal or vertical line from the linked list.
Construct a doubly linked list out of a ternary tree.
The task is to determine pairs in a doubly-linked list whose sum equals the provided value ‘val’ without consuming any extra space for a given sorted doubly-linked list of positive distinct entries. The expected complexities are O(n) time and O(1) space.
Given a 2-D matrix. You need to convert it into a linked list matrix such that each node is linked to its next right and down node and display it.
Extract all leaves from a Binary Tree into a Doubly Linked List (DLL).
Write a program to delete all odd positioned nodes from a circular linked list. (Consider 1-based indexing).
Why is merge sort a better option than quicksort for linked lists?