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?

Anonymous · Answer

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

Salesforce

Salesforce Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches