Reputation: 3007
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
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
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
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
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
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
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
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