cutting a list in half question..

This is a discussion on cutting a list in half question.. within the C Programming forums, part of the General Programming Boards category; i was presented with this function which cuts the first half of a list and returns the head but when ...

  1. #1
    Banned
    Join Date
    Oct 2008
    Posts
    1,535

    cutting a list in half question..

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

    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. #2
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    Quote Originally Posted by transgalactic2 View Post
    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
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  3. #3
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    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. #4
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    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
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  5. #5
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    ok i got the idea thanks

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting linked list please help with CODE
    By scarlet00014 in forum C Programming
    Replies: 3
    Last Post: 09-28-2008, 12:24 AM
  2. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 02:29 AM
  3. instantiated from here: errors...
    By advocation in forum C++ Programming
    Replies: 5
    Last Post: 03-27-2005, 09:01 AM
  4. Linked List Help
    By CJ7Mudrover in forum C Programming
    Replies: 9
    Last Post: 03-10-2004, 10:33 PM
  5. linked list stack question
    By Drew in forum C++ Programming
    Replies: 2
    Last Post: 09-11-2003, 06:05 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21