12
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ If the answers presented in this thread are what the interviewer expected, then this question doesn't test technical ability, but how well the candidate can dodge like a lawyer. $\endgroup$ – G. Bach Apr 20 '16 at 14:33
  • $\begingroup$ If double linked list take turns and iterate from both ends, make a comparison, stop once we found the same element from both (same pointer). or we can do do two from same end and count up one only on odd and stop when the furthest one reaches end, at that point returning the element of the position of the "only count the odds" one. $\endgroup$ – mathreadler Apr 20 '16 at 15:16
  • 2
    $\begingroup$ This is a terrible interview question because the it hinges critically on the term "pass" which is vague, ambiguous, subjective. Almost all good answers to this question involve abusing the definition so that you can effectively ignore it. $\endgroup$ – RBarryYoung Apr 20 '16 at 20:11
  • 2
    $\begingroup$ Well, the question raises a lot of discussion here. That means it is a good interview question in one respect: it starts you thinking. $\endgroup$ – Hendrik Jan Apr 20 '16 at 22:24
  • 2
    $\begingroup$ I so want to answer "read all of the elements into a vector, then access the element at position size()/2" $\endgroup$ – Cort Ammon Apr 20 '16 at 23:59
24
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Yeah, it's unclear whether this is a single pass. The question's unclear on that point. $\endgroup$ – David Richerby Apr 20 '16 at 15:47
  • 2
    $\begingroup$ By the way, this is related to the puzzle where you have two candles, one hour burning each, and you are asked to measure 45 minutes. $\endgroup$ – Hendrik Jan Apr 20 '16 at 15:47
  • 2
    $\begingroup$ Is this really any different then iterating the list, counting elements, and then iterating a second time to the half way point? All that's different is when you iterate the extra half. As @RBarryYoung mentions on the other similar answer, it really isn't a single pass, it's a pass and a half. $\endgroup$ – hatchet-inactive Apr 20 '16 at 21:06
  • 2
    $\begingroup$ If the list is long, moving both pointers "in parallel" will incur fewer cache misses than iterating from the beginning a second time. $\endgroup$ – zwol Apr 21 '16 at 0:48
  • 2
    $\begingroup$ This uses the same principle as the tortoise and hare algorithm for cycle detection. $\endgroup$ – Joshua Taylor Apr 21 '16 at 13:15
7
$\begingroup$

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;
}
$\endgroup$
  • $\begingroup$ Your second option is the correct answer (IMHO of course). $\endgroup$ – Matthew Crumley Apr 20 '16 at 15:35
  • 1
    $\begingroup$ It's actually making 1 1/2 passes over the linked list. $\endgroup$ – RBarryYoung Apr 20 '16 at 20:13
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How is this efficient? You are also iterating n times and not n/2. $\endgroup$ – Karan Khanna Apr 17 '18 at 7:40
3
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

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];

}
$\endgroup$
-3
$\begingroup$

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?

$\endgroup$
  • 6
    $\begingroup$ You don't know who downvoted what so your conclusion that one person downvoted everything may or may not be true but it certainly has no basis in facts available to you. But I'm downvoting your answer because we're looking for explanations, not piles of code. $\endgroup$ – David Richerby Apr 20 '16 at 22:20
  • $\begingroup$ It may be an assumption, but when I look one moment and less than 30 seconds later every post has exactly -1, it's not a unreasonable one. Even if it was 5 or 6 different people, not one of them left a comment why. But thank you for at least stating a reason. I don't get why a wordy explanation is better than code - yes, it's for a telephonic interview, but I'm not giving the OP a canned answer to regurgitate, I'm showing him a way to do it. I.E. I think downvoting a post because it has code is uncalled for, but thank you for at least saying why you did. $\endgroup$ – James K Apr 22 '16 at 17:35
  • $\begingroup$ Fair point -- it hadn't occurred to me that you could know the timing of the votes (having the page loaded while they happened is, I think, the only way ordinary users like us could find that out). We have a couple of meta posts about why we try to avoid actual code here: (1) (2). $\endgroup$ – David Richerby Apr 22 '16 at 18:16
  • $\begingroup$ Thanks for the meta links. I did read the FAQ, but I didn't see anything there - not that I would have noticed something like that, most likely, not something I would have expected. But I couldn't find anything when I rechecked after getting dinged, either. I may still be overlooking it, but I did look. The reasoning in the meta posts makes sense; thanks for the response. $\endgroup$ – James K Apr 24 '16 at 19:07
-5
$\begingroup$

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 .

$\endgroup$
  • $\begingroup$ This just duplicates Hendrick's answer. Please don't answer unless you have something new to say. $\endgroup$ – David Richerby Apr 21 '16 at 0:24

protected by Gilles Apr 20 '16 at 18:47

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?