My Weblog

Blog about programming and math

Linked List problems

Today i found a excellent link on linked list problems. It contains 18 problems with increasing difficulty. Its good for pointer exercise. Here are my solutions to 17 problems except merge sort. Although i tested these codes but i can’t say these codes are bug free. If you find any error or any improvement then please let me know.

#include<cstdio>
#include<iostream>
#include<cassert>
#include<cstdlib>
using namespace std;

struct node 
	{
		int data;
		struct node *next;
	};

void print(struct node *curr)
        {
                while(curr!=NULL) printf("%d -> ",curr->data),curr=curr->next;
                printf("\n");
        }


void push_front(struct node **ref,int n)
	{
		struct node *tmp=(struct node*) malloc ( sizeof (struct node ) );
		tmp->data=n;
		tmp->next=*ref;
		*ref=tmp;
	}
void push_back(struct node **ref,int n)
	{
		struct node *tmp=(struct node*) malloc (sizeof (struct node ));
		tmp->data=n;
		tmp->next=NULL;
		if(*ref==NULL) *ref=tmp;
		else 
		{
			struct node *curr=*ref;
			while(curr->next!=NULL) curr=curr->next;
			curr->next=tmp;		
		}

	}

int count(struct node *ref)
	{
		int cnt=0;
		struct node *curr=ref;
		while(curr!=NULL) cnt++,curr=curr->next;
		return cnt;
	}

int getNth(struct node *ref,int index)
	{
		struct node *tmp=ref;
		for(int i=0;ref!=NULL;i++)
		{
			if( i==index) return ref->data;
			ref=ref->next;
		}
		return -1;//case of failure
	}

int pop(struct node **ref)
	{
		assert(*ref!=NULL);//assert that 
		struct node *tmp=*ref;
		int data=tmp->data;
		*ref=tmp->next;
		tmp->next = NULL;
		return data;
	}

void insertNth(struct node **ref,int index,int n)
	{
		if(index==0) //inserting in front of the list so  need to modify the head address
		{
			struct node *tmp= (struct node *) malloc(sizeof (struct node));
			tmp->data=n;
			tmp->next=NULL;
			struct node *p=*ref;
			*ref=tmp;
			(*ref)->next=p;
			return;
		}
		else 
		{
			struct node *curr=*ref;
			for(int i=1;curr!=NULL;i++)
			{
				if(i==index)
				{
					struct node *tmp=(struct node *) malloc(sizeof (struct node));
					tmp->data=n;
					tmp->next=NULL;
					struct node *p=curr->next;
					curr->next=tmp;
					curr->next->next=p;
					return;
				}
				curr=curr->next;
			}
		}
	}

void sortedInsert(struct node **ref,int n)
	{
		if(*ref==NULL || (*ref)->data>n)//insertion at begining of list so we need to constantly update the address of head
		{
			
			struct node *tmp=(struct node *) malloc (sizeof (struct node ));
			tmp->data=n;
			tmp->next=NULL;
			if(*ref==NULL) *ref=tmp;
			else 
			{
				struct node *p=*ref;
				*ref=tmp;
				(*ref)->next=p;
			}
			return;
		}
		else 
		{

			struct node *curr=*ref;
			while(curr->next!=NULL && curr->next->data<n) curr=curr->next;
			struct node *tmp=(struct node *) malloc(sizeof (struct node ));
			tmp->data=n;
			tmp->next = NULL;
			struct node *p=curr->next;
			curr->next=tmp;
			curr->next->next=p;
			return;
		}
	}

//linked list sorting
void insertSort(struct node **ref)
	{
		struct node *tmp=*ref;
		*ref=NULL;
		while(tmp!=NULL) sortedInsert(ref,tmp->data),tmp=tmp->next;
	}

void append(struct node **ref_1,struct node **ref_2)
	{
		struct node *curr=*ref_1;
		while(curr->next!=NULL) curr=curr->next;
		curr->next=*ref_2;
		*ref_2=NULL;

	}

void frontbackSplit(struct node **ref,struct node **ref_1,struct node **ref_2)
	{
		*ref_1=*ref;
		struct node *slow=*ref,*fast=(*ref)->next;
		while(fast!=NULL && fast->next!=NULL) slow=slow->next,fast=fast->next->next;
		*ref_2=slow->next;
		slow->next=NULL;
		*ref=NULL;
	}

void removeDuplicates(struct node **ref)
	{
		struct node *curr=*ref;
		while(curr->next!=NULL)
		{
			if(curr->data == curr->next->data) curr->next= curr->next->next;
			else curr=curr->next;
		}
	}

void moveNode(struct node **ref_1,struct node **ref_2)
	{
		struct node *tmp=*ref_2;
		*ref_2=(*ref_2)->next;
		struct node *p=*ref_1;
		*ref_1=tmp;
		(*ref_1)->next=p;	
	}

void alternatingSplit(struct node **ref,struct node **ref_1,struct node **ref_2)
	{
		struct node *curr=*ref;
		while(true)
		{
			moveNode(ref_1,ref);
			if(*ref==NULL) break;
			moveNode(ref_2,ref);
			if(*ref==NULL) break;
		}
	}

void shuffleMerge(struct node **ref_1,struct node **ref_2)
	{
		struct node *curr_1=*ref_1,*curr_2=*ref_2,*t_1=(*ref_1)->next,*t_2=(*ref_2)->next;
		while(curr_1->next!=NULL && curr_2->next!=NULL)
		{
			curr_1->next=curr_2;
			curr_2->next=t_1;
			curr_1=t_1;
			curr_2=t_2;
			t_1=t_1->next;
			t_2=t_2->next;
		}
		if(curr_1->next==NULL) curr_1->next=curr_2;
		else  curr_2->next=curr_1;
	}

void sortedMerge(struct node **ref,struct node **ref_1,struct node **ref_2)
	{
		while(true)
		{
			if((*ref_1)->data<(*ref_2)->data)
			  {
				moveNode(ref,ref_1);
				if(*ref_1==NULL) break;
			  }
			else 
			 {
				moveNode(ref,ref_2);
				if(*ref_2==NULL) break;
			}
		}
		while(*ref_1!=NULL) moveNode(ref,ref_1);
		while(*ref_2!=NULL) moveNode(ref,ref_2);
	}
void sortedIntersect(struct node **ref,struct node *ref_1,struct node *ref_2)
	{
		struct node *curr_1=ref_1,*curr_2=ref_2;
		struct node *tmp=NULL;
		while(curr_1!=NULL && curr_2!=NULL)
		{
			if(curr_1->data == curr_2->data ) push_back(ref,curr_1->data),curr_1=curr_1->next,curr_2=curr_2->next;
			else if(curr_1->data<curr_2->data) curr_1=curr_1->next;
			else curr_2=curr_2->next;		
		}
	}

//this can also be solve by push_front or moveNode function 
void reverse(struct node **ref)
	{
		//assuming that list has more than 3 elements 
		struct node *p=(*ref),*q=p->next,*r=q->next;
		*ref=NULL;
		p->next=NULL;
		while(r!=NULL)
		{
			q->next=p;
			p=q;
			q=r;
			r=r->next;
		}
		q->next=p;
		*ref=q;
	}

void recursiveReverse(struct node *ref,struct node **h)
	{
		if(ref->next==NULL) 
		 {
			*h=ref;
			return;
		 }
		else 
		{
			recursiveReverse( ref->next,h);
			ref->next->next=ref;
			ref->next=NULL;
			return;
		}
	}	
int main()
	{

		struct node *head= NULL,*curr,*p=NULL,*q=NULL;
		for(int i=1;i<=11;i++) push_front(&p,i);printf("the p list is \n");print(p);
		for(int i=7;i<=33;i++)push_back(&q,i);printf("the q list is \n");print(q);
		printf("number of element in p %d\n",count(p));printf("number of element in q %d\n",count(q));
	printf("the  number at 3rd index in list p is %d\n",getNth(p,3));printf("the  number at 10th index in list q is %d\n",getNth(q,10));
		printf("the top element of list p is %d\n",pop(&p));	
		printf("the list p after popping th top element is \n");print(p);
		insertNth(&p,3,random());
		printf("inserting a random element in p at 3 rd index\n");print(p);
		printf("creating a new sorted linked list\n");
		struct node *r=NULL;
		for(int i=0;i<10;i++) sortedInsert(&r,random());print(r);
		insertSort(&p);printf("the list p after sorting \n"); print(p);
		struct node *s=NULL,*t=NULL;
		for(int i=0;i<10;i++) push_front(&s,random()),push_back(&t,random());
		printf("before appending the list s is \n");print(s); printf(" and the list t is\n");print(t);
		append(&s,&t);
		printf("after appending the list t to list s\n");print(s); 
		cout<<"reverse \n";recursiveReverse(p,&p); print(p);
		
	}
Advertisements

April 25, 2011 - Posted by | Programming

1 Comment »

  1. […] Testing code. print and push_back functions are taken from my previous implementation. […]

    Pingback by Reversing the linked list at some given position « My Weblog | January 9, 2013 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: