CareerCup

how abt using 2 pointers, one travelling twice as fast as the other. (lets call them the 'hare' and the 'tortoise'). both start at node 0, wen tortoise moves to the 1st node, hare is at node 2, and wen tortoise is at the nth node , hare is at the 2nth node. While jumping to the 2nth node, if the hare sees the end of the list, then the tortoise is moved one step back. As per the moral, "slow and steady" will give you the result !

that sounds about right.

Node* midList(Node *head)
{
struct node *fast, *slow;
slow=fast=head;
while(fast->next && fast->next->next)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}

for the function to find the mid of a linked list.
Initialize 2 pointer both pointing to the head of the list initially.
Now increment the first one by 2 places and keep the second one at rest. Keep moving the first pointer by 2 places and for each move of first pointer move the second pointer by one position. When the first pointer reaches to the end of linked list, second pointer will be pointing to the mid node.

for the Function to remove extra spaces in a string:

We can use the strtok function to get the tokens separated by spaces..(even if they are separated by multiple spaces). Store these tokens and once all the tokens are obtained, we can concatenate them with a single space between them. This way we are able to remove all the spaces and reconstruct the string with a single space between all the words.

the algo given by vel works absolutely fine.

I have two points to make :
- It didn't check for boundary cases.
- It did not exploit the information given for Doubly linked list. This information might not be required.

Are both singly/doubly linked list have the same implementation for this program?

node* mid(node* h)
{
	node *n, *m;
	if(!h) return 0;
	if(h->next==0) return h;
	n=h;
	m=h->next;
	while(m && m->next)
	{
		n=n->next;
		m=m->next->next;
	}
	return n;
}

node* mid(node* h)
{
	node *n, *m;
	if(!h) return 0;
	if(h->next==0) return h;
	n=h;
	m=h->next;
	while(m && m->next)
	{
		n=n->next;
		m=m->next->next;
	}
	return n;
}

if anyone knows how to have middle of linked list in O(1)???????

mohit, there doesn't exits such solution that gives you the mid in one shot, without traversing the list once.

node * linklist_mid(node *head)
{
node *s, *f;
s = f = head;

while(f && f->next) {
s = s->next;
f = f->next->next;
}

return s;
}

Create a double out of single and traverse half of it. O(1.5n) = O(n)

struct list *p,*q;
p=ptr;
q=p;
int flag=0;
while(q!=NULL)
{
if(flag==2)
{
p=p->next;
flag=0;
}
else
{
q=q->next;
flag++;

}
}

printf("\nValue at middle %d\n",p->value);

O(n)=O(1.5n).
Fail.