How to find the middle node of a single linked lis

Question

I have a problem statement like: "How to find the middle node of a singly linked list in only one traversal, and the twist is we don't know the number of nodes in the linked list?"

I have an answer like "take a vector and start pushing all the nodes' addresses as and when you are traversing the linked list and increment a counter till you reach the end of the list". So at the end we can get the number of nodes in the list and if even (counter/2) or if odd (counter/2 + counter%2) gives the middle node number and with this we can get vectore.at(middlenodenumber) points to the middle node".

This is fine...but this is waste of memory storing all the address of a very large linked list! So how can we have a better solution?

Answer 1

Use two pointers. Move first pointer by two nodes and second pointer by one node. When the first pointer reaches the end the second pointer will point to the middle.

Answer 2

Try this:
You have 2 pointers. one points to mid, and the other to the end, both point to beginning of the list at start. Every second time you successfully increment the end pointer you increment mid a once, until you end pointer reaches the end.

Answer 3

// How to find the middle node of a single linked list in a single traversal
//     1. The length of the list is not given
//     2. If the number of nodes is even, there are two middle nodes,
//        return the first one.
Node* MiddleNode(Node* const head)
{
    if (!head)
    {
        return head;
    }

    Node* p1 = head, * p2 = head->next;

    while (p2 && p2->next)
    {
        p1 = p1->next;
        p2 = p2->next->next;
    }

    return p1;
}

Answer 4

Say you have a std::list<T> l.

std::list<T>::iterator i = l.begin();
std::list<T>::iterator m = l.begin();
bool even = true;
while (i != list.end())
{
  if (even) ++m;
  ++i;
  even = !even;
}

Now m point to the middle of l.

Answer 5

SLNode* mid(SLNode *head) 

{

SLNode *one = head;

SLNode *two = head;


    while(one != nullptr) {
        one = one->next;
        two = two->next;
        if(one != nullptr) {
            one = one->next;
            //two = two->next;
        }
    }
    return two;
}

try this code

Answer 6

Following are the steps:

• Take two pointers *p1 and *p2 pointing to the head of linked list
• Start a loop and increment *p2, 2 times (with null checks)
• If *p2 is not null then increment *p1 1 time
• When *p2 reaches null; you have got the *p1 at the center

[Note: You can use iterators instead of pointer if you deal with container type linked list]