Programs on Linked List

Program to create a dummy single linked list

#include<stdio.h>

struct node

{

int data;

struct node *next;

};

typedef struct node * lnode;

main()

{

int ele,m,n,i;

lnode head=malloc(sizeof(struct node));

lnode temp,temp1;

if(head)

head->next=NULL;

addfirst(head,10);

temp1=head->next;

for(i=0;i<10;i++)

{

printf("enter the element to be added\n");

scanf("%d",&ele);

addfirst(head,ele);

}

print(head);

}

void addfirst(lnode head,int data)

{

lnode temp=malloc(sizeof(struct node));

temp->data=data;

temp->next=head->next;

head->next=temp;

}

void print(lnode head)

{

lnode temp=head->next;

while(temp)

{

printf("%d->",temp->data);

temp=temp->next;

}

printf("\n");

}

Given a singly-linked, find out the mid point of a single linked list

int middle(struct node *head)
{
struct node *slow,*fast;
slow=fast=head->next;
while(fast&&fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
}
return slow->data;
}

TC = Θ(n)
SC = O(1)

Program to check the loop in the single linked list

int findloop(lnode head)

{

lnode slow,fast;

slow=fast=head->next;

do

{

slow=slow->next;

if(fast==NULL || fast->next==NULL)

return 0;

fast=fast->next->next;

}

while(slow!=fast);

return 1;

}

TC = Θ(n)
SC = O(1)

Program to Reverse the single linked list

void reverse(lnode head)

{

lnode cur,temp;

cur=head->next;

head->next=NULL;

while(cur!=NULL)

{

temp=cur->next;

cur->next=head->next;

head->next=cur;

cur=temp;

}

}
Time Complexity (TC) = Θ(n)
Space Complexity (SC)= O(1)