By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
449,081 Members | 861 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 449,081 IT Pros & Developers. It's quick & easy.

Linked list in C

P: n/a
MJ
Hi
I have written a prog for reversing a linked list
I have used globle pointer
Can any one tell me how I can modify this prog so that I dont have to
use extra pointer Head1.
When I reverse a LL using the recursive call how to change the last
node pointer to head and head->next to null without using the extra
global pointer
Mayur

----------------------------------------
//This is the program to create a linkedlist
// and reverse the linkedlist
#include <iostream.h>
#include <malloc.h>
//------------------------------------------
typedef struct node
{
int value;
struct node *next;
}mynode;
//------------------------------------------
//Global Variables
mynode *head,*tail,*temp, *head1;
//------------------------------------------
//Display the contents of the linked list
Display()
{
mynode *temp1;
temp1 = head;
while (temp1) {
cout << temp1->value << "\n";
temp1 = temp1->next;
}
return 0;
}
//------------------------------------------
//Append a node in the linked list
void Add(int value)
{
temp = (mynode *) malloc(sizeof(mynode));
//temp = new mynode;
//temp = (mynode *) malloc(sizeof(mynode*));
temp->value = value;
temp->next = (mynode *)0;
if(head == (mynode *)0) {
head = temp;
}
else
{
mynode *temp1;
temp1 =head;
while(temp1->next != (mynode*)0){
temp1 = temp1->next;
}
temp1->next = temp;
}
}
//------------------------------------------
//Reverse the linked list
mynode * reverse(mynode *ptr)
{
mynode *temp1;
if(!(ptr && ptr->next))
{
head1 = ptr;
return ptr;
}
temp1 = reverse(ptr->next);
temp1->next = ptr;
if(head == ptr)
{
head->next = (mynode*)0;
head = head1;
}
return ptr;
}
//------------------------------------------
//Delete the linked list
void Delete()
{
while(head)
{
mynode *temp;
temp = head;
head = head->next;
free(temp);
//delete temp;

}
}
//------------------------------------------
//Main Program
int main(void)
{
for (int i =1 ; i <= 5; i++) {
Add(i*i*i);
}
Display();
reverse(head);
cout << "--------------------\n";
Display();
//Delete();

// for (i =1 ; i <= 5; i++) {
// Add(i*i*i);
// }
// Display();
// reverse(head);
// cout << "--------------------\n";
// Display();
// Delete();
return 0;
}
//------------------------------------------

Nov 15 '05 #1
Share this Question
Share on Google+
4 Replies


P: n/a
On Fri, 01 Jul 2005 01:57:47 -0700, MJ wrote:
Hi
I have written a prog for reversing a linked list
I have used globle pointer
Can any one tell me how I can modify this prog so that I dont have to
use extra pointer Head1.
When I reverse a LL using the recursive call how to change the last
node pointer to head and head->next to null without using the extra
global pointer
Mayur

----------------------------------------
//This is the program to create a linkedlist
// and reverse the linkedlist
#include <iostream.h>


Your first problem is to decide which language you are writing in. You
arew posting to comp.lang.c but your code isn't valid C. If you want to
write C++ code post to comp.lang.c++. What might be considered to be a
good answer to your question could be different there.

Lawrence

Nov 15 '05 #2

P: n/a
"MJ" <ma********@gmail.com> wrote in message
news:11**********************@g44g2000cwa.googlegr oups.com...
Hi
I have written a prog for reversing a linked list
I have used globle pointer
Can any one tell me how I can modify this prog so that I dont have to
use extra pointer Head1.


It's called a doubly-linked list. You have forward and backward links.

--
Mabden
Nov 15 '05 #3

P: n/a
MJ wrote:

I have written a prog for reversing a linked list. I have used
globle pointer. Can any one tell me how I can modify this prog
so that I dont have to use extra pointer Head1. When I reverse
a LL using the recursive call how to change the last node pointer
to head and head->next to null without using the extra global
pointer


.... snip off topic C++ code ...

Here is a C package:

/* List handling, reversal, sort, merge, split */
/* file listops.h */
/* By C.B. Falconer. Public Domain, use as you wish */
/* Attribution appreciated. */
/* ================== 30 April, 2001 ================== */

#ifndef listops_h_
#define listops_h_

#include <stddef.h> /* NULL */
#include <iso646.h> /* not, and */

/* The bare minimum to form a linked list */
typedef struct node {
struct node *next;
void *data;
} node, *nodeptr;

/* ================================================== ===== */
/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root);

/* ================================================== ===== */
/* split list p into 2 nearly equal lists, return 2nd part */
nodeptr splitlist(nodeptr p);

/* ================================ */
/* Merge two ordered lists into one */
nodeptr mergelists(nodeptr p1, nodeptr p2,
int (*cmp)(void*, void*)); /* compare */

/* ================================================== */
/* Recursively sort a linked list. The sort is stable */
/* This is an O(NlogN) process for all lists. */
nodeptr mergesort(nodeptr root,
int (*cmp)(void*, void*)); /* compare */

#endif
/* end listops.h */
/* List handling, reversal, sort, merge, split */
/* file listops.c */
/* By C.B. Falconer. Public Domain, use as you wish */
/* Attribution appreciated. */
/* ================== 30 April, 2001 ================== */

#include "listops.h"

/* ================================================== ===== */
/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root)
{
nodeptr curr, nxt;

if (root) { /* non-empty list */
curr = root->next;
root->next = NULL; /* terminate new list */
while (curr) {
nxt = curr->next; /* save for walk */
curr->next = root; /* relink */
root = curr; /* save for next relink */
curr = nxt; /* walk onward */
}
}
/* else empty list is its own reverse; */
return root;
} /* revlist */

/* ================================================== ===== */
/* split list p into 2 nearly equal lists, return 2nd part */
nodeptr splitlist(nodeptr p)
{
nodeptr p1, p2, p3;

p1 = p2 = p3 = p;
if (not p) return NULL;
do {
p3 = p2;
p2 = p2->next; /* advance 1 */
p1 = p1->next;
if (p1) p1 = p1->next; /* advance 2 */
} while (p1);

/* now form new list after p2 */
p3->next = NULL; /* terminate 1st half */
return p2;
} /* splitlist */

/* ================================ */
/* Merge two ordered lists into one */
nodeptr mergelists(nodeptr p1, nodeptr p2,
int (*cmp)(void *, void*)) /* compare */
{
node n;
nodeptr p;

p = &n;
n.next = p;

while (p1 and p2) {
if (cmp(p1, p2) <= 0) {
p->next = p1; p = p1; p1 = p1->next;
}
else {
p->next = p2; p = p2; p2 = p2->next;
}
}
/* at least one list now empty, copy other */
/* one or both of these operations is null */
if (p1) p->next = p1;
if (p2) p->next = p2;

/* check for empty lists */
if (n.next == &n) return NULL;
return n.next;
} /* mergelists */

/* ================================================== */
/* Recursively sort a linked list. The sort is stable */
/* This is an O(NlogN) process for all lists. */
nodeptr mergesort(nodeptr root,
int (*cmp)(void *, void*)) /* compare */
{
nodeptr p;

if (root and root->next) { /* 2 up items in list */
p = splitlist(root); /* alters list root */
root = mergelists(mergesort(root, cmp),
mergesort( p, cmp),
cmp);
}
/* else the unit or empty list is already sorted */

return root;
} /* mergesort */

/* end listops.c */

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 15 '05 #4

P: n/a

"CBFalconer" <cb********@yahoo.com> wrote in message
news:42***************@yahoo.com...
MJ wrote:

I have written a prog for reversing a linked list. I have used
globle pointer. Can any one tell me how I can modify this prog
so that I dont have to use extra pointer Head1. When I reverse
a LL using the recursive call how to change the last node pointer
to head and head->next to null without using the extra global
pointer


... snip off topic C++ code ...

Here is a C package:

/* List handling, reversal, sort, merge, split */
/* file listops.h */
/* By C.B. Falconer. Public Domain, use as you wish */
/* Attribution appreciated. */
/* ================== 30 April, 2001 ================== */

#ifndef listops_h_
#define listops_h_

#include <stddef.h> /* NULL */
#include <iso646.h> /* not, and */

/* The bare minimum to form a linked list */
typedef struct node {
struct node *next;
void *data;
} node, *nodeptr;

/* ================================================== ===== */
/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root);

/* ================================================== ===== */
/* split list p into 2 nearly equal lists, return 2nd part */
nodeptr splitlist(nodeptr p);

/* ================================ */
/* Merge two ordered lists into one */
nodeptr mergelists(nodeptr p1, nodeptr p2,
int (*cmp)(void*, void*)); /* compare */

/* ================================================== */
/* Recursively sort a linked list. The sort is stable */
/* This is an O(NlogN) process for all lists. */
nodeptr mergesort(nodeptr root,
int (*cmp)(void*, void*)); /* compare */

#endif
/* end listops.h */
/* List handling, reversal, sort, merge, split */
/* file listops.c */
/* By C.B. Falconer. Public Domain, use as you wish */
/* Attribution appreciated. */
/* ================== 30 April, 2001 ================== */

#include "listops.h"

/* ================================================== ===== */
/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root)
{
nodeptr curr, nxt;

if (root) { /* non-empty list */
curr = root->next;
root->next = NULL; /* terminate new list */
while (curr) {
nxt = curr->next; /* save for walk */
curr->next = root; /* relink */
root = curr; /* save for next relink */
curr = nxt; /* walk onward */
}
}
/* else empty list is its own reverse; */
return root;
} /* revlist */

/* ================================================== ===== */
/* split list p into 2 nearly equal lists, return 2nd part */
nodeptr splitlist(nodeptr p)
{
nodeptr p1, p2, p3;

p1 = p2 = p3 = p;
if (not p) return NULL;
do {
p3 = p2;
p2 = p2->next; /* advance 1 */
p1 = p1->next;
if (p1) p1 = p1->next; /* advance 2 */
} while (p1);

/* now form new list after p2 */
p3->next = NULL; /* terminate 1st half */
return p2;
} /* splitlist */

/* ================================ */
/* Merge two ordered lists into one */
nodeptr mergelists(nodeptr p1, nodeptr p2,
int (*cmp)(void *, void*)) /* compare */
{
node n;
nodeptr p;

p = &n;
n.next = p;

while (p1 and p2) {
if (cmp(p1, p2) <= 0) {
p->next = p1; p = p1; p1 = p1->next;
}
else {
p->next = p2; p = p2; p2 = p2->next;
}
}
/* at least one list now empty, copy other */
/* one or both of these operations is null */
if (p1) p->next = p1;
if (p2) p->next = p2;

/* check for empty lists */
if (n.next == &n) return NULL;
return n.next;
} /* mergelists */

/* ================================================== */
/* Recursively sort a linked list. The sort is stable */
/* This is an O(NlogN) process for all lists. */
nodeptr mergesort(nodeptr root,
int (*cmp)(void *, void*)) /* compare */
{
nodeptr p;

if (root and root->next) { /* 2 up items in list */
p = splitlist(root); /* alters list root */
root = mergelists(mergesort(root, cmp),
mergesort( p, cmp),
cmp);
}
/* else the unit or empty list is already sorted */

return root;
} /* mergesort */

/* end listops.c */

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!


Good.
Would there be any benefit in making this into a library, rather than just
keeping a copy of the c file around for inclusion in a project?
Nov 15 '05 #5

This discussion thread is closed

Replies have been disabled for this discussion.