XXXXXX.working.in.my.blood wrote:

hi all,

i need help with linked lists...

the problem is this, "reverse the contents of a singly linked list

without using a temporary node"...

solution with code will be appreciated...

I can't imagine how a temporary node would be helpful.

/* BEGIN list.h */

#ifndef H_LIST

#define H_LIST

typedef struct list_node {

struct list_node *next;

void *data;

} list_type;

list_type *list_make(long unsigned);

list_type *list_rev(list_type *);

list_type *list_sort(list_type *,

int (*)(const list_type *, const list_type *));

void list_free(list_type *, void (*)(void *));

#endif

/* END list.h */

/* BEGIN list.c */

#include <stdlib.h>

#include "list.h"

static long unsigned list_count(list_type *);

static list_type *node_sort(list_type *, long unsigned,

int (*)(const list_type *, const list_type *));

static list_type *list_merge(list_type *, list_type *,

int (*)(const list_type *, const list_type *));

static list_type *list_split(list_type *, long unsigned);

list_type *list_rev(list_type *head)

{

list_type *next_node, *previous;

if (head != NULL) {

next_node = head -> next;

head -> next = NULL;

while (next_node != NULL) {

previous = next_node -> next;

next_node -> next = head;

head = next_node;

next_node = previous;

}

}

return head;

}

list_type *list_make(long unsigned count)

{

list_type *node, *list;

list = count != 0 ? malloc(sizeof *list) : NULL;

if (list != NULL) {

node = list;

while (--count != 0) {

node -> data = NULL;

node -> next = malloc(sizeof *node -> next);

if (node -> next == NULL) {

list_free(list, free);

return NULL;

} else {

node = node -> next;

}

}

node -> data = NULL;

node -> next = NULL;

}

return list;

}

void list_free(list_type *node, void (*free_data)(void *))

{

list_type *next_node;

while (node != NULL) {

next_node = node -> next;

free_data(node -> data);

free(node);

node = next_node;

}

}

list_type *list_sort(list_type *head,

int (*compar)(const list_type *, const list_type *))

{

return node_sort(head, list_count(head), compar);

}

static long unsigned list_count(list_type *head)

{

long unsigned count;

for (count = 0; head != NULL; head = head -> next) {

++count;

}

return count;

}

static list_type *node_sort(list_type *head, long unsigned count,

int (*compar)(const list_type *, const list_type *))

{

long unsigned half;

list_type *tail;

if (count > 1) {

half = count / 2;

tail = list_split(head, half);

tail = node_sort(tail, count - half, compar);

head = node_sort(head, half, compar);

head = list_merge(head, tail, compar);

}

return head;

}

static list_type *list_split(list_type *head, long unsigned count)

{

list_type *tail;

while (count-- > 1) {

head = head -> next;

}

tail = head -> next;

head -> next = NULL;

return tail;

}

static list_type *list_merge(list_type *head, list_type *tail,

int (*compar)(const list_type *, const list_type *))

{

list_type *list, *sorted, **node;

node = compar(head, tail) > 0 ? &tail : &head;

sorted = list = *node;

*node = sorted -> next;

while (*node != NULL) {

node = compar(head, tail) > 0 ? &tail : &head;

sorted -> next = *node;

sorted = *node;

*node = sorted -> next;

}

sorted -> next = head != NULL ? head : tail;

return list;

}

/* END list.c */

/* BEGIN list_sort.c */

#include <stdio.h>

#include <stdlib.h>

#include "list.h"

#define NODES 17

#define LU_RAND_SEED 123456789LU

#define LU_RAND(S) ((S) * 69069 + 362437 & 0xffffffff)

struct score {

float literature;

float history;

float sociology;

};

int hist_score_comp(const list_type *, const list_type *);

void score_init(list_type *, long unsigned);

void score_print(list_type *);

int main(void)

{

list_type *score;

score = list_make(NODES);

if (score == NULL) {

fputs("The score list was not allocated.\n", stderr);

exit(EXIT_FAILURE);

}

score_init(score, LU_RAND_SEED);

puts("BEGIN output from list_sort.c\n\nRandom order");

score_print(score);

puts("Sorted on history");

score = list_sort(score, hist_score_comp);

score_print(score);

puts("Reverse Sorted order");

score = list_rev(score);

score_print(score);

puts("END output from list_sort.c\n");

list_free(score, free);

return 0;

}

void score_init(list_type *node, long unsigned seed)

{

while (node != NULL) {

node -> data = malloc(sizeof (struct score));

if (node -> data == NULL) {

fputs("malloc problem\n", stderr);

exit(EXIT_FAILURE);

}

seed = LU_RAND(seed);

((struct score *)node -> data) -> literature

= seed % 40 + 60.0f;

seed = LU_RAND(seed);

((struct score *)node -> data) -> history

= seed % 40 + 60.0f;

seed = LU_RAND(seed);

((struct score *)node -> data) -> sociology

= seed % 40 + 60.0f;

node = node -> next;

}

}

void score_print(list_type *node)

{

float score;

while (node != NULL) {

score = ((struct score *)node -> data) -> literature;

printf("literature %d ", (int)score);

score = ((struct score *)node -> data) -> history;

printf("history %d ", (int)score);

score = ((struct score *)node -> data) -> sociology;

printf("sociology %d\n", (int)score);

node = node -> next;

}

putchar('\n');

}

int hist_score_comp(const list_type *head, const list_type *tail)

{

float first = ((struct score *)head -> data) -> history;

float second = ((struct score *)tail -> data) -> history;

return second > first ? -1 : second != first;

}

/* END list_sort.c */

--

pete