How to find middle element of linked list in one pass?

Question

One of the most popular question from data structures and algorithm, mostly asked on telephonic interview.

Answer 1

By cheating, and doing two passes at the same time, in parallel. But I do not know whether the recruiters will like this.

Can be done on a single linked list, with a nice trick. Two pointers travel over the list, one with double speed. When the fast one reaches the end, the other one is half-way.

Answer 2

If it's not a doubly linked list, you could just count and use a list, but that requires doubling your memory in the worst case, and it simply won't work if the list is too large to store in memory.

A simple, almost silly solution, is just increment the middle node every two nodes

function middle(start) {
    var middle = start
    var nextnode = start
    var do_increment = false;
    while (nextnode.next != null) {
        if (do_increment) {
             middle = middle.next;
        }
        do_increment = !do_increment;
        nextnode = nextnode.next;
    }
    return middle;
}

Answer 3

Elaborating on Hendrik's answer

If it's a doubly linked list, iterate from both ends

function middle(start, end) {
  do_advance_start = false;
  while(start !== end && start && end) {
     if (do_advance_start) {
        start = start.next
     }
     else {
        end = end.prev
     }
     do_advance_start = !do_advance_start
  }
  return (start === end) ? start : null;
}

Given [1, 2, 3] => 2

1, 3
1, 2
2, 2

Given [1, 2] => 1

1, 2
1, 1

Given [1] => 1

Given [] => null

Answer 4

Create a structure with a pointer capable of pointing to nodes of linked list and with an integer variable which keeps count of the number of nodes in the list.

struct LL{
    struct node *ptr;
    int         count;
}start;

Now store the address of the first node of linked list in $start.ptr$ and initialize $start.count = 1$.
Ensure that the value of $start.count$ is incremented by one after the successfull creation of a new node in linked list. Similarly, decrement it by one whenever a node is deleted from the linked list.

Use $start.count$ to find the middle element in one single pass.

Answer 5

Create a dynamic array, where each element of the array is a pointer to each node in the list in traversing order, starting from the beginning. Create an integer, initialized to 1, that keeps track of how many nodes you have visited (which increments each time you go to a new node). When you get to the end, you know how big the list is, and you have an ordered array of pointers to each node. Finally, divide the size of the list by 2 (and subtract 1 for 0-based indexing) and fetch the pointer held in that index of the array; if the size of the list is odd, you can choose which element to return (I will still return the first one).

Here is some Java code which gets the point across (even though the idea of a dynamic array will be a bit wonky). I would provide C/C++ but I am very rusty in that area.

public Node getMiddleNode(List<Node> nodes){

    int size = 1;
    //add code to dynamically increase size if at capacity after adding
    Node[] pointers = new Node[10];

    for (int i = 0; i < nodes.size(); i++){
        //remember to dynamically allocate more space if needed
        pointers[i] = nodes.get(i);
        size++;
    }

    return pointers[(size - 1)/2];

}

Answer 6

Is recursion considered more than one pass?

Traverse the list to the end, passing an integer count by reference. Make a local copy of that value at each level for later reference, and increment the ref count going into the next call.

On the last node, divide the count by two and truncate/floor() the result (if you want the first node to be the "middle" when there are only two elements) or round up (if you want the second node to be the "middle"). Use a zero- or one-based index appropriately.

Unwinding, match the ref count to the local copy (which is the node's number). If equal, return that node; else return the node returned from the recursive call.
.

There are other ways to do this; some of them may be less cumbersome (I thought I saw someone say read it into an array and use the array length to determine the middle - kudos). But frankly, there are no good answers, because it's a stupid interview question. Number one, who still uses linked lists (supporting opinion); Two, finding the middle node is an arbitrary, academic exercise with no value in real-life scenarios; Three, if I really needed to know the middle node, my linked list would expose a node count. It's hella easier to maintain that property than to waste time traversing the entire list every time I want the middle node. And finally, four, every interviewer is going to like or reject different answers - what one interviewer thinks is slick, another will call ridiculous.

I almost always answer interview questions with more questions. If I get a question like this (I never have), I would ask (1) What are you storing in this linked list, and is there a more appropriate structure to efficiently access the middle node if there is truly a need to do so; (2) What are my constraints? I can make it faster if memory is not an issue (e.g. the array answer), but if the interviewer thinks bulking up memory is wasteful, I'll get dinged. (3) What language will I be developing in? Nearly every modern language I know of has built-in classes to deal with linked lists that make traversing the list unnecessary - why reinvent something that has been tuned for efficiency by the developers of the language?

Answer 7

By using 2 pointers . Increment one at each iteration and other at every second iteration. When 1st pointer points to end of linked list, went 2nd pointer will point to the middle mode of linked list .