reverse a link list

[Neo]

Hi Frns,

Could U plz. suggest me how can i reverse a link list (without recursion)???

here is my code (incomplete):



#include<stdio.h>

#include<stdlib.h>

#define MAX_NODES 8

typedef struct node {

int data;

struct node *next;

} NODE;



void reverse_list(NODE **head)

{

/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */

/* TODO: Reverse the List here. */

/* ___________________________ */


return;

}



int main()

{

NODE *head, *tmp;

int i;

head = malloc(sizeof(NODE));

if(!head) return 1;

head->data = 1;

head->next = NULL;

tmp = head;

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

{

tmp->next = malloc(sizeof(NODE));

if(!tmp->next) break;

tmp->next->data = i + 2;

tmp = tmp->next;

}

reverse_list(&head);

tmp = head;

while(tmp)

{

printf("%d\n", tmp->data);

tmp = tmp->next;

}

return 0;

}

-Neo

 

[Nick Keighley]

Could U plz. suggest me how can i reverse a link list (without

recursion)???

assuming the original list is in old_list and the reversed list will be
created in new_list

WHILE old_list not empty
get item from head of old_list
add item to tail of new_list

 

[Chris Croughton]

recursion)???

assuming the original list is in old_list and the reversed list will be
created in new_list

WHILE old_list not empty
get item from head of old_list
add item to tail of new_list

I think you mean "add item to head of new_list":

old list item new list
removed
12345 1 1
2345 2 21
345 3 321
45 4 4321
5 5 54321

(Assuming that the 'head' of a list is on the left.)

Chris C

 

[dandelion]

recursion)???

assuming the original list is in old_list and the reversed list will be
created in new_list

WHILE old_list not empty
get item from head of old_list
add item to tail of new_list

Ummmm...

Woundn't that give you exactly the same list?

I'd suggest:

WHILE old_list not empty
get item from head of old_list
add item to head of new_list

So the last item of old_list is the head of new_list.

 

[Neo]

recursion)???

assuming the original list is in old_list and the reversed list will be
created in new_list

WHILE old_list not empty
get item from head of old_list
add item to tail of new_list

Nick Keighley

Well,

I've implemented it as follows, its working fine.
Is there any possibility to optimize reverse_list() further :


#include<stdio.h>
#include<stdlib.h>

#define MAX_NODES 8

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

void reverse_list(NODE **head)
{
NODE *t;
NODE *newlist = NULL;

while(*head) {
t = *head; /*** Take out an element off the head ***/
*head = (*head)->next;

/*** Add it in front of newlist ***/
if(!newlist) {
t->next = 0;
newlist = t;
}
else {
t->next = newlist;
newlist = t;
}
}
*head = newlist;
}


int main()
{
NODE *head, *tmp;
int i;

head = malloc(sizeof(NODE));
if(!head) return 1;
head->data = 1;
head->next = NULL;
tmp = head;

for(i=0; i < MAX_NODES; i++)
{
tmp->next = malloc(sizeof(NODE));
if(!tmp->next) break;
tmp->next->data = i + 2;
tmp = tmp->next;
}
tmp->next = NULL;

reverse_list(&head);
tmp = head;
while(tmp)
{
printf("%d\n", tmp->data);
tmp = tmp->next;
}

return 0;
}

 

[Kevin D. Quitt]

....

/*** Add it in front of newlist ***/

if(!newlist) {
t->next = 0;
newlist = t;
}
else {

The if-else is superfluous. newlist contains a NULL so both branches of
the if are guaranteed to do the same thing.

 

[CBFalconer]

Could U plz. suggest me how can i reverse a link list (without recursion)???

It's an easy thing to do. However we don't do homework, and we
also don't respond well to people who use kewl abreviations.

 

[Neo]

...


The if-else is superfluous. newlist contains a NULL so both branches of
the if are guaranteed to do the same thing.

Yeah! right.
Thanks Kevin!

 

[Derrick Coetzee]

Could U plz. suggest me how can i reverse a link list (without recursion)???

Although this wasn't your question, it's interesting to note that
reversing a doubly-linked list in-place is much easier. Simply swap the
prev and next pointers on each node:

struct node {
/* data */
struct node* next;
struct node* prev;
};

void reverse_dll(struct node* node) {
while(node != NULL) {
struct node* nextNode = node->next;
node->next = node->prev;
node->prev = nextNode;
node = nextNode;
}
}

 

[pete]

Well,

I've implemented it as follows, its working fine.
Is there any possibility to optimize reverse_list() further :

#include<stdio.h>
#include<stdlib.h>

#define MAX_NODES 8

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

void reverse_list(NODE **head)
{
NODE *t;
NODE *newlist = NULL;

while(*head) {
t = *head; /*** Take out an element off the head ***/
*head = (*head)->next;

/*** Add it in front of newlist ***/
if(!newlist) {
t->next = 0;
newlist = t;
}
else {
t->next = newlist;
newlist = t;
}
}
*head = newlist;
}

int main()
{
NODE *head, *tmp;
int i;

head = malloc(sizeof(NODE));
if(!head) return 1;
head->data = 1;
head->next = NULL;
tmp = head;

for(i=0; i < MAX_NODES; i++)
{
tmp->next = malloc(sizeof(NODE));
if(!tmp->next) break;
tmp->next->data = i + 2;
tmp = tmp->next;
}
tmp->next = NULL;

reverse_list(&head);
tmp = head;
while(tmp)
{
printf("%d\n", tmp->data);
tmp = tmp->next;
}

return 0;
}

/* BEGIN new.c */

#include<stdio.h>
#include<stdlib.h>

#define MAX_NODES 8

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


NODE *reverse_list(NODE *head)
{
NODE *previous, *next_node;

if (head != NULL) {
next_node = NULL;
while (head -> next != NULL) {
previous = head;
head = previous -> next;
previous -> next = next_node;
next_node = previous;
}
head -> next = next_node;
}
return head;
}


int main(void)
{
NODE *head, *tmp;
int i;

head = malloc(sizeof(NODE));
if (head == NULL) {
exit(EXIT_FAILURE);
}
head -> data = 1;
head -> next = NULL;
tmp = head;
for (i = 0; MAX_NODES > i; ++i) {
tmp -> next = malloc(sizeof *(tmp -> next));
if (tmp -> next == NULL) {
break;
}
tmp -> next -> data = i + 2;
tmp = tmp -> next;
}
tmp -> next = NULL;
head = reverse_list(head);
tmp = head;
while (tmp != NULL) {
printf("%d\n", tmp -> data);
tmp = tmp -> next;
}
free(head);
return 0;
}

/* END new.c */

 

[CBFalconer]

.... snip ...

/* BEGIN new.c */

#include<stdio.h>
#include<stdlib.h>

.... snip ...

Here is my version, and some more. This has been published here
before.

/* 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 ================== */
/* using stdops.h, 16 Sept. 2001 */

#include "stdops.h" /* bool, true, false, not, and, or, xor */
#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 */

 

[pete]

/* BEGIN new.c */

#include<stdio.h>
#include<stdlib.h>

#define MAX_NODES 8

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

NODE *reverse_list(NODE *head)
{
NODE *previous, *next_node;

if (head != NULL) {
next_node = NULL;
while (head -> next != NULL) {
previous = head;
head = previous -> next;
previous -> next = next_node;
next_node = previous;
}
head -> next = next_node;
}
return head;
}

void list_free(NODE *node)
{
NODE *next_node;

while (node != NULL) {
next_node = node -> next;
free(node);
node = next_node;
}
}

int main(void)
{
NODE *head, *tmp;
int i;

head = malloc(sizeof(NODE));
if (head == NULL) {
exit(EXIT_FAILURE);
}
head -> data = 1;
head -> next = NULL;
tmp = head;
for (i = 0; MAX_NODES > i; ++i) {
tmp -> next = malloc(sizeof *(tmp -> next));
if (tmp -> next == NULL) {
break;
}
tmp -> next -> data = i + 2;
tmp = tmp -> next;
}
tmp -> next = NULL;
head = reverse_list(head);
tmp = head;
while (tmp != NULL) {
printf("%d\n", tmp -> data);
tmp = tmp -> next;
}

free(head);

Change that to

list_free(head);