Auxiliary 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 the given linked list is 1->2->3->4->5->6 then the output should be 4.
Question
Auxiliary 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 the given linked list is 1->2->3->4->5->6 then the output should be 4.
Solution
To solve this problem, we can use the two-pointer technique. Here are the steps:
- Initialize two pointers, slow_ptr and fast_ptr, to head of the linked list.
- Move slow_ptr by one and fast_ptr by two.
- When fast_ptr reaches the end of the linked list, slow_ptr will be at the middle of the linked list.
Here is the Python code for the above steps:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def findMiddle(head):
slow_ptr = head
fast_ptr = head
if head is not None:
while(fast_ptr is not None and fast_ptr.next is not None):
fast_ptr = fast_ptr.next.next
slow_ptr = slow_ptr.next
return slow_ptr.data
In the above code, we first define a Node class to represent each node in the linked list. Then we define a function findMiddle that takes the head of the linked list as input and returns the data of the middle node. Inside the function, we initialize slow_ptr and fast_ptr to head. Then we enter a loop that continues until fast_ptr reaches the end of the linked list. Inside the loop, we move fast_ptr by two and slow_ptr by one. When the loop ends, slow_ptr will be at the middle of the linked list, so we return its data.
Similar Questions
Which of the following algorithm is the optimal way to find the middle element of the linked list?radio_button_uncheckedFind the length of the Linked List and then traverse again to the n/2th Noderadio_button_unchecked Fast and slow pointer methodradio_button_uncheckedFind the distance of all nodes and print the middle nodesradio_button_uncheckedNone of these
How is the last node identified in a doubly linked list?
Which type of linked list has its last node pointing back to the first node?a.Singly linked listb.Circular linked listc.Linear linked listd.Doubly linked list
Remove the Middle Node of a Linked ListWrite a function to remove the middle node of a linked list.Constraints:NAExample:Sample Input:512345Sample Output:Original list: 5 4 3 2 1 List after deleting middle node: 5 4 2 1 Explanation:Enter the number of elements to insert: 5Enter the elements:1 2 3 4 5Output:Original list: 5 4 3 2 1 List after deleting middle node: 5 4 2 1 Public Test Cases:# INPUT EXPECTED OUTPUT1 512345Original list: 5 4 3 2 1 List after deleting middle node: 5 4 2 1
In a singly linked list, the last node references to : a) Head b) NULL c) Next node d) None of the above
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.