DSA - Data Structures & Algorithms

 

Q1.How do you identify the middle node of a doubly linked list?

The most efficient way to find the middle node of a doubly linked list is by using the Two Pointer (Slow and Fast Pointer) technique. Algorithm Initialize two pointers: slow → starts at the head. fast → also starts at the head. Move: slow by one node at a time. fast by two nodes at a time. When fast reaches the end of the list (or fast->next becomes NULL), slow will be pointing to the middle node.

while (fast->next != NULL &&
       fast->next->next != NULL)
{
    slow = slow->next;
    fast = fast->next->next;
}

  struct Node
{
    int data;
    struct Node *prev;
    struct Node *next;
};

struct Node* findMiddle(struct Node *head)
{
    if (head == NULL)
        return NULL;

    struct Node *slow = head;
    struct Node *fast = head;

    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}
  

---