Thread: cutting a list in half question..

1. cutting a list in half question..

i was presented with this function which cuts the first half of a list

but when i compiled it .i get a bug
i cant see the idea in this code
how i cuts by half??

Code:
```#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int value;
struct node *next;
}Node;

Node * what1(Node *  source);
int main()
{
Node *p;
p=(Node *)malloc(sizeof(Node));
p->value=1;
p->next=(Node *)malloc(sizeof(Node));
p->next->value=2;
p->next->next=(Node *)malloc(sizeof(Node));
p->next->next->value=3;
p->next->next->next=(Node *)malloc(sizeof(Node));
p->next->next->next->value=4;

what1(p);
free(p);
return 0;
}

Node* what1(Node *  source)
{
Node *fast,*slow,*temp;
if (source==NULL||source->next==NULL)
return source;
slow=fast=source;
do
{
temp=slow;
slow=slow->next;
fast=fast->next;
if(fast)
fast=fast->next;
free(temp);

}while(fast);
return slow;
}```

2. Originally Posted by transgalactic2
i cant see the idea in this code
how i cuts by half??
This is the hare and tortoise approach, also known as Classic Floyd's Cycle Finding Algorithm. You have two pointers "fast" and "slow". The fast pointer advances two list items per iteration, the slow pointer only one. Hence, if the fast pointer reaches the end of the list, the slow pointer is approximately in the middle of the list.

Your code doesn't check whether fast==slow. Thus, if your list is cyclic, it will result in an endless loop. Computing the middle of a list is just a nice side-effect.

It's also unusual to free the list while cutting it in halves, because then the result is useless. I'm too lazy to analyze your code: what is the bug?

Greets,
Philip

3. the bug is that on some point it wants to accsess fast->next
but fast is null so i get a bug

how to prevent it?

4. the bug is that on some point it wants to accsess fast->next
but fast is null so i get a bug
Each "fast->next" is preceded by a test if fast==NULL, so there shouldn't be any problems. On my system, the code compiles fine and the function indeed computes the middle of the list.

Greets,
Philip

5. ok i got the idea thanks