Question: A singly linked list is a list in which a pointer p has two values; ke

Question

Question: A singly linked list is a list in which a pointer p has two values; key(p) and next(p) (thus there is no previous(p)). A pass on a singly linked list starts with the assignment of a finite number of pointers to the start of the list, and then moving the pointers further in the list (there is no restriction on how much the pointers can go forward but they cannot go backward).

Given a 2n size Linked list with s pointing to the head of the list, design a single pass algorithm that returns the n'th (or middle) item in the list. Use as few pointers as you can.

If you find it hard to do it in one pass, give a two pass algorithm that finds the n number in the list.

Explanation / Answer

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
struct node
{
    int data;
    struct node* next;
};
void push(struct node** ref, int datanew)
{

    struct node* nnode =
    (struct node*) malloc(sizeof(struct node));
     nnode->data = datanew;
     nnode->next = (*ref);
     (*ref)    = nnode;
}

int GetNth(struct node* head11, int index11)
{
    struct node* curr = head11;
    int cnt = 0;
    while (curr != NULL)
    {
       if (cnt== index11)
          return(curr->data);
       cnt++;
       curr = curr->next;
    }


    assert(0);            
}

int main()
{

    struct node* head11 = NULL;
   
     push(&head11, 1);
    push(&head11, 4);
    push(&head11, 1);
    push(&head11, 12);
    push(&head11, 1);

    printf("The Element at index 3 is %d", GetNth(head11, 3));
    getchar();
}

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.