CODEWITHSUNDEEP
c++
d3vdpro
d3vdpro

Reputation: 3007

middle of linked list

how to find the middle of the linked list when we are not informed of its size and it must be performed using only one loop and only one pointer.

Upvotes: 0

Views: 3798

Answers (7)

uss
uss

Reputation: 1309

The C++ way to find the middle of the list since you have tagged c++:

#include <list> 
using namespace std;

using IntegerList = list<int>; 

int main() { 
     IntegerList l; 
     for (int i : {0, 1, 2, 3, 4, 5, 6})
          l.push_back(i * 1); 

     auto m = l.begin(); 
     bool even = false; 
     for(auto &z:l) { 
         if (even) ++m; 
         even = !even; 
     }

     cout << "\nmiddle of the list:" << *m << "\n";
}

Upvotes: -1

Rushil
Rushil

Reputation: 11

We can use skip list in this case:

1) While traversing each node in the Linked List make a skip list of the odd numbered nodes. Time: O(n) Space: O(n/2)

2) Now when you reach the end of the list divide the legnth by 2 and add 1 to get the middle element index.

3) Search for the index in the skip list O(logn) time.

So, Overall Time Complexity of the algorithm would be :

O(n)(1 traversal) + O(logn)(Searching Skip list) = O(n) Space Complexity : O(n/2)

Please reply if this is inefficient....

Upvotes: 1

Jonathan Graehl
Jonathan Graehl

Reputation: 9301

Node *m,*e,*head; /* head is given */
m=e=head;
while(e) {
  e=e->next;
  if (e) {
    e=e->next;
    m=m->next;
  }
}
/* now m is the middle node */

Sorry, I had to use 2 pointers :)

Adding this to your answer, because a minor tweak reduces the number of pointers to 1. I hope you don't mind:

Node m,*e,*head; /* head is given */
e = head;
if (e) m = *e;
while(e) {
  e = e->next;
  if (e) {
    e = e->next;
    m = *(m.next);
  }
}
/* now m is the middle node */

Upvotes: 8

Paul Hanbury
Paul Hanbury

Reputation: 981

How about

LinkedList * llist = getLList(); // the linked list
Node * node = llist.head;

while ( node ) {
    node = node.next;
    if ( node ) {
        node  = node.next;
        llist.remove( llist.head );
    }
}
// now llist.head is (er, um... was) the middle node.  
// hope you didn't need the rest of the list.

Upvotes: 13

Test
Test

Reputation: 1727

see my code. it works on my FC9 x86_64 correctly, the function "middle()" is that what you want:

static struct node *middle(struct node *head)
{
        struct node *mid = head;
        int flag = 0;
        while (NULL != head) {
                head = head->next;
                flag = !flag;
                if (flag) {
                        mid = mid->next;
                }
        }
        return mid;
}

EDIT: remove code except the middle().

Upvotes: 1

Rob Pelletier
Rob Pelletier

Reputation: 327

Iterate over your list using the provided head pointer and increment your one allowed pointer (I assume from your ambiguously-worded question that you're allowed one pointer besides the one that was passed in) once for every two increments of the head pointer.

Node* middle( Node* head )
{
    Node* middle = head;
    while (head != NULL) {
        head = head->next;

        if (head->next != NULL) {
            head = head->next;
            middle = middle->next;
        }
    }
    return middle;
}

There are edge cases ignored here (like what's the middle of a list with an even number of elements).

Upvotes: 0

rlbond
rlbond

Reputation: 67857

Well, it's sort of a hack, since it's functionally equivalent to 2 loops. But still, it is only 1 loop.

Node* middle(Node* const begin)
{
    Node* current = begin;
    bool size_known = false;
    int size = 0;
    while (true)
    {
        if (!size_known)
        {
            if (current)
            {
                ++size;
                current = current->next;
            }
            else
            {
                current = begin;
                size_known = true;
            }
        }
        else
        {
            if (size <= 1)
                return current;
            current = current->next;
            size -= 2;
        }
    }
}

Upvotes: 2

Related Questions