CODEWITHSUNDEEP
c++linked-list
srinuvenu
srinuvenu

Reputation: 485

How to find the middle node of a single linked list in a single traversal (if the length of the list is not given)

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?

Upvotes: 5

Views: 16773

Answers (7)

RajatRusty
RajatRusty

Reputation: 1

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

Upvotes: 0

Peter Lee
Peter Lee

Reputation: 13809

// 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;
}

Upvotes: 0

Oswald
Oswald

Reputation: 31647

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.

Upvotes: 10

iammilind
iammilind

Reputation: 69988

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]

Upvotes: 26

Jeeva
Jeeva

Reputation: 4663

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.

Upvotes: 0

atoMerz
atoMerz

Reputation: 7672

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.

Upvotes: 0

Bj&#246;rn Pollex
Bj&#246;rn Pollex

Reputation: 76788

You can use a single loop with two iterators, say it1 and it2, where you increment it2 only every second iteration of the loop. Terminate when it1 has reached the end of the list. it2 will now point to the middle element of the list.

Upvotes: 1

Related Questions