Linked Lists - hard exercise(help needed)


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 7 of 7

Thread: Linked Lists - hard exercise(help needed)

  1. #1
    Join Date
    Feb 2006
    Posts
    3

    Linked Lists - hard exercise(help needed)

    hello
    i came across a really difficult exercise about linked lists..
    and i cant seem to solve it

    here's the question

    there's a doubly linked list which is also circled (i.e the last node's next pointer points to the head of the list,and the head's prev pointer points to the last node).

    the data in each node is an integer.

    now a jump in a circular list is as follows:
    if we have a node p :
    if p.data is positive we move p.data times using the next pointer
    if p.data is negative we move p.data times using the prev pointer
    if p.data is 0 we dont move at all.

    now you need to write a method that recieves as a paramater a pointer to the head of the list , and returns true if threre's a path that starts from the head node and ends there.

    an example:
    2-->14-->-5--> 1-->-4-->1

    for this list the method will return true,because we start with 2 ,move to -5,
    then move to 1(moving backwords) ,then -4 ,and then 2.

    this is not homework(i'm working on different exercises in order to prepare my self to an exam)

    help will be appreciated..
    thank you very much.

  2. #2
    Join Date
    Dec 2005
    Location
    New Jersey
    Posts
    290
    What have you tried?

  3. #3
    Join Date
    Feb 2006
    Posts
    3
    i only had one idea concerning the distance between the nodes,but i couldn't develop it,so i'm actually in a dead end.

    i just can't seem to grasp the principle of this question

    and of course my main problem is :when should i return false.

    just forgot to mention: you are not allowed to create new objects
    Last edited by parallel; 02-04-2006 at 11:42 AM.

  4. #4
    Join Date
    Dec 2005
    Location
    New Jersey
    Posts
    290
    Well, think about it logically. We return true if after going through the sequence we return at the head. Well, if we come back to any other number besides the head, it will never read the head.
    eg: 1, 1, 2. This will go from position 0 to 1, then 1 to 2, then 2 to 1. We know that this will never reach the head again.

    Hope this helps!

  5. #5
    Join Date
    Dec 2005
    Location
    New Jersey
    Posts
    290
    Okay here's something that does what you want. I purposely used another object because I know you're not allowed.
    Code:
    ArrayList<Integer> index = new ArrayList<Integer>();
    int position = 0;
    while (!index.contains(position)) {
        index.add(position);
        position = (linkedList.get(position) + position) % linkedList.size();
        if (position < 0) {
            position += linkedList.size();
        }
    }
    if (position == 0) {
        System.out.println("good!");
    } else {
        System.out.println("bad!");
    }

  6. #6
    Join Date
    Feb 2006
    Posts
    3
    thank you very much..i'll go over it now,and see if i get the idea

    thanks again.

  7. #7
    Join Date
    Aug 2013
    Posts
    1

    I have developed follwing code for your question

    #include<stdio.h>
    #include<stdlib.h>
    typedef struct node
    {
    int info;
    struct node *prev;
    struct node *next;
    }NODE;

    NODE *create_doublylist(NODE *,int);
    int path(NODE *);
    void display(NODE *);
    NODE *start=NULL;

    int main()
    {
    int i,info,n;
    printf("\nPlease enter the number of elements in the circular doubly list:");
    scanf("%d",&n);
    printf("\nEnter the elements:");
    for(i=0;i<n;i++)
    {
    scanf("%d",&info);
    start=create_doublylist(start,info);
    }
    printf("\nThe list is given by:");
    display(start);
    if(path(start))
    printf("\nThat path exist:");
    else
    printf("\nPath does not exist:");
    return(0);
    }
    NODE *create_doublylist(NODE *start,int info)
    {
    NODE *temp=(NODE *)malloc(sizeof(NODE));
    temp->info=info;
    NODE *ptr=start;
    if(start==NULL)
    {
    start=temp;
    start->prev=temp;
    start->next=temp;
    return start;
    }
    while(ptr->next!=start)
    ptr=ptr->next;
    temp->prev=ptr;
    ptr->next=temp;
    temp->next=start;
    start->prev=temp;
    return start;
    }

    int path(NODE *ptr)
    {
    int i,c=ptr->info;
    NODE *temp=ptr;
    printf("%d-->",c);
    if(c>=0)
    {
    for(i=1;i<=c;i++)
    ptr=ptr->next;
    }
    else
    {
    c=-c;
    for(i=1;i<=c;i++)
    ptr=ptr->prev;
    }
    if(ptr==start)
    {
    printf("%d",ptr->info);
    return 1;
    }
    else if(ptr==temp)
    return 0;
    //printf("%d-->",ptr->info);
    path(ptr);
    }
    void display(NODE *start)
    {

    NODE *ptr=start;
    do
    {
    printf("%d ",ptr->info);
    ptr=ptr->next;
    }while(ptr!=start);
    printf("\n");
    }

Similar Threads

  1. linked lists [was: its urgent]
    By limu in forum C++
    Replies: 7
    Last Post: 06-18-2005, 06:56 AM
  2. Problem with linked lists and iterators
    By white94cam in forum C++
    Replies: 2
    Last Post: 03-31-2005, 12:02 AM
  3. LINKED SERVER PROBLEM (help needed URGENT)
    By Madhavi in forum Database
    Replies: 1
    Last Post: 06-28-2002, 12:53 PM
  4. Dynamic linked lists !!!
    By Vidula in forum Java
    Replies: 0
    Last Post: 12-01-2000, 05:26 AM
  5. Replies: 1
    Last Post: 10-22-2000, 05:29 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center