Fastest way to find the middle node in a linked list

Question

Kais · Accepted Answer

you walk the linked list with 2 pointers, one advancing on each pass, the second advancing every other pass, The second pointer will reach the middle of the list by the time the first one reaches the end.

node *findmiddle(node *head) {
node *walker = head;
node *middle = head;
boolean_t moveit = TRUE;

if (head == NULL)
    return; // trivial case;

while (walker ->next != NULL) {
    walker = walker->next;
    if (moveit)
          middle = middle->next;
    moveit = ~moveit;
}
return middle;
}

Jigargosha · Answer

node* FindMiddle(node* head)
{
    if (!head)
        return null; // error 
        
    node* fast = head; // fast pointer
    
    while (fast->next && fast->next->next) // fast->next->next will not be evaluated in fast->next == null
    {
        head = head->next;
        fast = fast->next->next;                    
    }
    
    return head;
}

hivejin · Answer

ListNode findMiddle(ListNode head) {
    if(head == null || head.next == null)
        return head;
    ListNode slow = head, fast = head;
    while(fast != null, fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

rokuboku · Answer

how's that the middle node?

Sigiloso · Answer

Why wouldn't you just check the head, and then do list.get(list.size()/2)?

Salesforce

Pergunta de entrevista da empresa Salesforce

Respostas da entrevista

Empresas seguidas

Buscas de vagas