reversing a singly linked list

**galmca** · 02-07-2005

i'll be very thankful if u can help me out here ...i have to write a program in c language ...to REVERSE A LINKED LIST.i have tried it until the point where the reversal is not used coz i don't know the logic which will be used to reverse a linked list....for example if a list is there like: 0->1->2->3->4->5->6
then the reverse of linked list would be 6->5->4->3->2->1->0.
i have tried it partially though...plz help me out and i'll be very greatful to u if u can help me in the reversing code....i've done something like this...

Code:

#include<stdio.h>
#include<conio.h>
struct link
{
int data;
struct link*ptr;
};
typedef struct link node;
int main()
{
int i,size;
node*start,*temp,*p,*last;
clrscr();
printf("enter the size of list");
scanf("%d",&size);
start=NULL;
for(i=0;i<size;i++)
{
 if(start==NULL)
   {
       start=(node*)malloc(sizeof(node));
       printf("enter the elements of list\n");
       scanf("%d",&start->data);
       start->ptr=NULL;
   }
  else
    {
  for(p=start;p->ptr!=NULL;p=p->ptr)
  temp=(node*)malloc(sizeof(node));
  scanf("%d",&temp->data);
  p->ptr=temp;
  temp->ptr=NULL;
    }
}
//now what do i do?after this?here the reverse of a linked list is to be done.....plz help me here..

**rjv_rnjn** · 02-07-2005

You are a gem galmca. Your persistence with your indentation style is rock solid, nobody can move you. As you can make out I'm n00b to this forum and was going through the previous posts and found one of your posts locked. God knows, whom will you listen to!

**PING** · 02-07-2005

Ah, dont worry much about galmca, galmca and cgod are our resident demons. nobody minds them..

btw galmca, for reversing, you would have to use recursions..

something like

Code:

 void reverse(void *startaddr)
 { 
    if(startaddr->next==NULL )
     {
       // print the data in the node
     }
    reverse(startaddr->next)
     // print the data in the node
}

and please please please indent that code of yours

**pianorain** · 02-07-2005

You shouldn't have to use recursion. It seems simple enough. Pseudo-code follows:

Code:

set a temp pointer to the head of the list
set a back pointer to NULL
while the temp pointer is not at the end of the list
{
   store a next pointer to the next node
   set temp pointer's next to the back pointer
   set the back pointer to this node
   set the temp pointer to the next pointer
}
head of the list = back pointer

**Thantos** · 02-07-2005

Theres only one problem: This is a single direction link list as indicated by his title. The only way to reverse a single direction link list is to basically build another list. This is why the majority of lists are two directional link lists, so you can go forward and backwards.

**pianorain** · 02-07-2005

For the benefit of the OP, I wasn't going to actually write any code, but I want to make sure I'm thinking correctly. Please excuse any syntax errors; this is still meant as pseudo-code.

Code:

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

node* reverse(node* head)
{
   node *temp, *back, *next;
   for(temp = head, back = NULL; temp != NULL; temp = next)
   {
      next = temp->next;
      temp->next = back;
      back = temp;
   }
   return back;
}

On a list with 2 nodes:

Code:

Head of List: Node 1
Node 1 (next:Node 2)
Node 2 (next:NULL)

Call reverse(Node 1)

In reverse:
temp = Node 1
back = NULL
while (temp != NULL)
   next = Node 2
   Node 1 -> next = NULL
   back = Node 1
   temp = Node 2
while (temp != NULL)
   next = NULL
   Node 2 -> next = Node 1
   back = Node 2
   temp = NULL
return Node 2

Reversed list:
Head of List: Node 2
Node 1 (next:NULL)
Node 2 (next:Node 1)

**itsme86** · 02-07-2005

You definitely don't need recursion:

Code:

itsme@dreams:~/C$ cat revllist.c
#include <stdio.h>
#include <malloc.h>

typedef struct node_s
{
  int num;
  struct node_s *next;
} NODE;

void show_list(NODE *list)
{
  while(list)
  {
    printf("%d ", list->num);
    list = list->next;
  }
  putchar('\n');
}

int main(void)
{
  NODE *list = NULL, *temp = NULL, *n;
  int i;

  for(i = 0;i < 5;++i)
  {
    if(!(n = malloc(sizeof(NODE))))
    {
      puts("Memory allocation error!");
      return 1;
    }
    n->num = i + 1;
    n->next = list;
    list = n;
  }

  printf("Original List: ");
  show_list(list);

  while(list)
  {
    n = list->next;
    list->next = temp;
    temp = list;
    list = n;
  }
  list = temp;

  printf("Reversed List: ");
  show_list(list);

  while(list)
  {
    n = list->next;
    free(list);
    list = n;
  }

  return 0;
}

Code:

itsme@dreams:~/C$ ./revllist
Original List: 5 4 3 2 1
Reversed List: 1 2 3 4 5

Thread: reversing a singly linked list

Thread Tools

Search Thread

Display

reversing a singly linked list

Similar Threads

Reverse function for linked list

Anyone good with linked list.....I am not....

How can I traverse a huffman tree

Contest Results - May 27, 2002

singly linked list