Link List

I am solving the helpfree challenge in the main site "In-Place linked list reversing"

My problem is that I don't know what link list should I use. I made a simple one

Code:

struct lilist{
	int val;
	lilist* node;
} ;
lilist *fad;
lilist* listinit(){
	fad=new lilist;
	return fad;
}
lilist* put(int p){
	static lilist *ad=fad;
	ad->val=p;
	ad->node=new lilist;
	ad->node->node=NULL;
	//cout<<ad<<"  "<<ad->node<<endl;
	ad=ad->node;
	
	return ad->node;
}

int get(bool f=false){
	static lilist* as = fad;
	if(f) {as=fad; return 0;}
	int ret=as->val;

	if(as->node!= NULL) 
		as=as->node;
	else return 0;
	return ret;

}

Is this enough for the challenge?

Can you do it without using any static variables or any globals?

Neither are very good if you want to make a list which is useful.

I think I can. But because challenge is not about making a link list, I don't want to wast my time on it. I only want to know if my LL functionality is enough for challenge or not.

Depends on how you plan to reverse it.

I guess you could try it as it stands, and see what happens.
If it doesn't work, at least you'll learn something.

Please read the challenge and tell me is this possible or not.
http://www.cprogramming.com/helpfree.html

Jeez, you could have done it by now and found the answer.

It's just another "will this work?" thread.
The answer being "why don't you spend 5 minutes finding out rather than wasting hours on a message board thread" (looks at clock - 1h45m gone already).

If I say "yes", and you can't do it, what are you going to do - blame me for bad advice ?

I don't know what an standard link list needs.

It needs a pointer to the next element in the list

If I understand "in-place" correctly, it would be a lot simpler with a double-linked list, where you should have a pointer to the previous node, too.

But maybe I misunderstand it and you can use the simple implementation.

Code:

while node is not null
  temp = node->next
  node->next = othernode
  othernode = node
  node = temp
end while
head = othernode

It should be singly linked list.
I am going to build a more advanced link list, I will place it here.

This is my new linked list no globals no statics

Code:

struct linklist{
	int val;
	linklist* node;
} ;

linklist* list_init(){
	linklist *address =new linklist;
	address->node=NULL;
	return (address);
}

linklist* getNodeAddress(linklist* address, int pos=-1){
	if(pos>=0) 
		for(int i = 0; i<pos;i++)
			if(address->node!=NULL) address=address->node;
			else break;
	else
		while(address->node!=NULL) address=address->node;
	return address;
}

int getNodeValue(linklist* address, int pos=-1){
	return getNodeAddress(address, pos)->val;
}

void setNodeValue(linklist* address,int value, int pos=-1){
	address=getNodeAddress(address, pos);
	address->val=value;
	address->node=new linklist;
	address->node->node = NULL;
}

int getNodeCount(linklist* address){
	int count=0;
	while(address->node!=NULL) {
		count++; 
		address=address->node;	
	}
	return count;
}

int destroyAllNodes(linklist* address){
	int count=0;
	while(address->node!=NULL) {
		count++; 
		linklist* nextNodeAddress=address->node;
		delete[] address;
		address=nextNodeAddress;
	}
	delete[] address;
	return count;
}

Here is the debugged version with a test code

Code:

#include<iostream>
using namespace std;

struct linklist{
	int val;
	linklist* node;
} ;

linklist* list_init(){
	linklist *address =new linklist;
	address->node=NULL;
	return (address);
}
int getNodeCount(linklist* address){
	int count=0;
	while(address->node!=NULL) {
		count++; 
		address=address->node;	
	}
	return count;
}

linklist* getNodeAddress(linklist* address, int pos=-1, bool read=false){
	if(pos>=0)
		for(int i = 0; i<pos;i++)
			if(address->node!=NULL && !(read && address->node->node==NULL)) 
				address=address->node;
			
			else break;
	else
		while(address->node!=NULL && !(read && address->node->node==NULL)) address=address->node;
	return address;
}


int getNodeValue(linklist* address, int pos=-1){
	return getNodeAddress(address,pos,true)->val;
	
}

void setNodeValue(linklist* address,int value, int pos=-1){
	int nCount=getNodeCount(address);
	if(pos>nCount) throw 1;
	address=getNodeAddress(address, pos);
	if(address->node!=NULL) address->val=value;
	else {
		address->val=value;
		address->node=new linklist;
		address->node->node = NULL;
	}
}


int destroyAllNodes(linklist* address){
	int count=0;
	while(address->node!=NULL) {
		count++; 
		linklist* nextNodeAddress=address->node;
		delete[] address;
		address=nextNodeAddress;
	}
	delete[] address;
	return count;
}

int main(){
	linklist *hList = list_init();
	
	for(int i=0;i<10;i++) setNodeValue(hList,i);
	int limit = getNodeCount(hList);

	for(int i=0; i<limit/2;i++){
		int p =getNodeValue(hList,limit-i-1);
		setNodeValue(hList,getNodeValue(hList,i),limit-i-1);
		setNodeValue(hList,p,i);	
	}

	limit = getNodeCount(hList);
	cout<<"After reverse"<<endl;
	for(int i=0; i<limit;i++) cout<<getNodeValue(hList,i)<<endl;


	cin.get();
	return 0;
}

The latest code seems to reverse the values in the list but leaves the nodes in place, which would be one way to reverse the values. To test your understanding of linked lists can you do it by switching nodes rather than values in nodes? For example, you could switch the first node with the last, the second node with the second to last node, the third node with the third to last node, etc.

for(i = 0; i < halfTheNodesInTheList; ++i)
FindNodeA
FindNodeB
SwitchNodesAandB

I did something:

Code:

#include<iostream>
using namespace std;

struct linklist{
	int val;
	linklist* node;
} ;

linklist* list_init(){
	linklist *address =new linklist;
	address->node=NULL;
	return (address);
}
int getNodeCount(linklist* address){
	int count=0;
	while(address->node!=NULL) {
		count++; 
		address=address->node;	
	}
	return count;
}

linklist* getNodeAddress(linklist* address, int pos=-1, bool read=false){
	if(pos>=0)
		for(int i = 0; i<pos;i++)
			if(address->node!=NULL && !(read && address->node->node==NULL)) 
				address=address->node;
			
			else break;
	else
		while(address->node!=NULL && !(read && address->node->node==NULL)) address=address->node;
	return address;
}


int getNodeValue(linklist* address, int pos=-1){
	return getNodeAddress(address,pos,true)->val;
	
}

void setNodeValue(linklist* address,int value, int pos=-1){
	int nCount=getNodeCount(address);
	if(pos>nCount) throw 1;
	address=getNodeAddress(address, pos);
	if(address->node!=NULL) address->val=value;
	else {
		address->val=value;
		address->node=new linklist;
		address->node->node = NULL;
		address->node->val = 666;
	}
}

linklist* swapNodes(linklist* address, int node1, int node2){
	linklist* n1=NULL,*n2=NULL,*p1=NULL,*p2=NULL,*tmp;
	cout<<node1<<"  "<<node2<<endl;
	int count=getNodeCount(address);
	if(node1 > count || node2 >count){cout<<"if"<<endl; return NULL;}
	if(node1 > -1){ n1= getNodeAddress(address, node1);}
	if(node2 > -1)  n2= getNodeAddress(address, node2);
	if(node1-1 >= 0)  p1= getNodeAddress(address, node1-1);
	else p1 = NULL;
	if(node2-1 >= 0)  p2= getNodeAddress(address, node2-1);
	else p2= NULL;
	if(p1!=NULL && p2!=NULL && (p1 == n2 || p2 == n1)) {
		p1->node=n1->node;
		tmp=n2->node;
		n2->node=n1;
		n1->node=tmp;
		return address;
	}
	else if(p1==NULL && p2!=NULL && (p1 == n2 || p2 == n1)){
		
		tmp=n2->node;
		n2->node=address;
		n1->node=tmp;
		return n2;
	
	}
	else if(p1!=NULL && p2==NULL && (p1 == n2 || p2 == n1)){
		tmp=n1->node;
		n1->node=address;
		n2->node=tmp;
		return n1;
	}
	else{
		tmp= n1->node;
		n1->node=n2->node;
		n2->node= tmp;
	
	
		if(p1!=NULL && p2!= NULL){
			tmp=p1->node;
			p1->node=p2->node;
			p2->node=tmp;
			return address;
		}

		else if(p1==NULL) {cout<<"NULL"<<endl;tmp= p2->node; p2->node=address; return tmp;}
		else if(p2==NULL) {cout<<"NULL"<<endl;tmp= p1->node; p1->node=address; return tmp;}
		else {cout<<"else"<<endl; return NULL;}
	}
	
}
int destroyAllNodes(linklist* address){
	int count=0;
	while(address->node!=NULL) {
		count++; 
		linklist* nextNodeAddress=address->node;
		delete[] address;
		address=nextNodeAddress;
	}
	delete[] address;
	return count;
}

int main(){
	linklist *hList = list_init();
	
	for(int i=0;i<10;i++) setNodeValue(hList,i);
	int limit = getNodeCount(hList);
	for(int i=0; i<limit;i++) cout<<getNodeAddress(hList,i)<<" -> "<<getNodeAddress(hList,i)->node<<"  "<<getNodeValue(hList,i)<<endl;
	for(int i=0; i<limit/2;i++){
		int p =getNodeValue(hList,limit-i-1);
		setNodeValue(hList,getNodeValue(hList,i),limit-i-1);
		setNodeValue(hList,p,i);	
	}
	
		

	limit = getNodeCount(hList);
	cout<<"After reverse"<<endl;
	for(int i=0; i<limit;i++) cout<<getNodeAddress(hList,i)<<" -> "<<getNodeAddress(hList,i)->node<<"  "<<getNodeValue(hList,i)<<endl;
	cout<<endl;
	for(int i=0; i<limit/2;i++){
		if((hList = swapNodes(hList,i,limit-i-1)) == NULL) break;
	}
	for(int i=0; i<limit;i++) cout<<getNodeAddress(hList,i)<<" -> "<<getNodeAddress(hList,i)->node<<"  "<<getNodeValue(hList,i)<<endl;
	cout<<endl;
	hList = swapNodes(hList,0,1);
	for(int i=0; i<limit;i++) cout<<getNodeAddress(hList,i)<<" -> "<<getNodeAddress(hList,i)->node<<"  "<<getNodeValue(hList,i)<<endl;
	cout<<endl;

	cin.get();

	return 0;
}

You're heading down the wrong path!

I suggest learning the concept of Push, and Pop, in terms of stacks implemented using linked lists.