Reversing Singly Linked List Easily

jai_steave 0 Tallied Votes 428 Views Share

This will works Recusivly and easily

void rev(node *h,node *myparentaddr)
{
if(h->next!=NULL)
{
rev(h->next,h);
tail=h;
}
else
head=h;
h->next=myparentaddr;
}

call it in main by rev(head,NULL);
jai_steave 0 Newbie Poster

it works recursively

Duoas 1,025 Postaholic Featured Poster

Nice, but it fails on three counts:
1. It doesn't return the new head of the list.
2. It fails if h is NULL.
3. It fails on really big lists (stack overflow).

Here's an iterative solution you might enjoy.

/*
  Reverse a singly linked list without recursion.
  The argument may be NULL.
  Returns the new head of the list.
  Runs in linear time and with constant memory usage.
 */
node *rev( node *head ) {
  node *next;
  node *curr = head;
  node *prev = NULL;

  while (curr != NULL) {
    next       = curr->next;
    curr->next = prev;

    prev       = curr;
    curr       = next;
    }

  return prev;
  }

Call it thus: head = rev( head ); Enjoy!

farwa 0 Newbie Poster

hello every one i m new to c language can any one help me in typing a marksheet in c.

jessel 0 Newbie Poster

hello do you have a program in c that deals in linked list?
please help me

biswarup.nandi.71 0 Newbie Poster
#include <stdio.h>
#include <conio.h>

struct linked_list
{
    int info;
    struct linked_list *next;
};

typedef struct linked_list node;

/*prototypes*/

void create(node*);
int pt(node*);
void insertnode(node*);
void append(node*);
node* insertstart(node*);
void removenode(node*);
void removeend(node*);
node* removestart(node*);

main()
{
    node *head;
    int c;

    clrscr();

    head = (node*)malloc(sizeof(node));

    create(head);
    c = pt(head);
    printf("\nNo. of nodes : %d\n" , c);

    printf("\nInserting new node -> ");
    insertnode(head);
    c = pt(head);
    printf("\nNo. of nodes : %d\n" , c);

    printf("\nInserting new node at end");
    append(head);
    c = pt(head);
    printf("\nNo. of nodes : %d\n" , c);

    printf("\nInserting new node at start");
    head = insertstart(head);
    c = pt(head);
    printf("\nNo. of nodes : %d\n" , c);

    printf("\n\nPress any key to begin deletion ->-> \n");
    getch();

    printf("\nDeleting a node at start ->\n");
    head = removestart(head);
    c = pt(head);
    printf("\nNo. of nodes : %d\n" , c);

    printf("\nDeleting a node at any position ->\n");
    removenode(head);
    c = pt(head);
    printf("\nNo. of nodes : %d\n" , c);

    printf("\nDeleting a node at end ->\n");
    removeend(head);
    c = pt(head);
    printf("\nNo. of nodes : %d\n" , c);

    system("pause");
    return 0;
}

void create(node *list)
{
    printf("\nEnter data : ");
    printf("\nType -999 to stop ");
    scanf("%d" , &list->info);

    if(list->info == -999)
        list->next = NULL;
    else
    {
        list->next = (node*)malloc(sizeof(node));
        create(list->next);
    }
}

int pt(node *list) //count
{
    int c;
    c = 0;
    while(list->next != NULL)
    {
        printf("%d " , list->info);
        list = list->next;
        c++;
    }
    return c;
}

void insertnode(node *list)
{
    int pos , c;
    node *temp;
    c = 0;

    printf("\nEnter position where node is to be inserted : ");
    scanf("%d" , &pos);

    while(list->next != NULL)
    {
        c++;
        if(c == pos)
        {
            temp = (node*)malloc(sizeof(node));
            temp->next = list->next;
            list->next = temp;
            printf("\nEnter value in next node : ");
            scanf("%d" , &temp->info);
            break;
        }
        list = list->next;
    }
}

void append(node *list)
{
    node *temp , *temp2;
    while(list->next->info != -999)
        list = list->next;
    temp2 = list->next;
    temp = (node*)malloc(sizeof(node));
    list->next = temp;
    temp->next = temp2;
    printf("\nEnter value in new node : ");
    scanf("%d" , &temp->info);
}

node* insertstart(node *list)
{
    node *temp;
    temp = (node*)malloc(sizeof(node));
    printf("\nEnter value in new node : ");;
    scanf("%d" , &temp->info);
    temp->next = list;
    list = temp;
    return list;
}

void removenode(node *list)
{
    int pos , c;
    /*node *temp;
    temp = list;
    list = list->next;*/
    c = 0;

    printf("\nEnter position where node is to be removed : ");
    scanf("%d" , &pos);

    while(list->next != NULL)
    {
        c++;
        if(c == pos-1)
        {
            /*temp->next = list->next;*/
            list->next = list->next->next;
            break;
        }

        list = list->next;
        /*temp = temp->next;*/
    }
}

void removeend(node *list)
{
    node *temp;
    temp = list;
    list = list->next;

    while(list->next->info != -999)
    {
        list = list->next;
        temp = temp->next;
    }

    temp->next = list->next;

    /*
        OR WE CAN USE

        while(list->next->next->info != -999)
            list = list->next;
        list->next = list->next->next;
    */
}

node* removestart(node *list)
{
    list = list->next;
    return list;
}
rustysynate 0 Newbie Poster

This code snippet is from stanford library. It's elegant and simple. Some parts get tricky, it's better to have a drawing to understand it better.

void RecursiveReverse(struct node** headRef) {
    struct node* first;
    struct node* rest;
    if (*headRef == NULL) return;       // empty list base case
    first = *headRef;           // suppose first = {1, 2, 3}
    rest = first->next;             // rest = {2, 3}
    if (rest == NULL) return;       // empty rest base case
    RecursiveReverse(&rest);        // Recursively reverse the smaller {2, 3} case
                                    // after: rest = {3, 2}
    first->next->next = first;      // put the first elem on the end of the list
    first->next = NULL;             
    *headRef = rest;            // fix the head pointer
}
deceptikon 1,790 Code Sniper Team Colleague Featured Poster

It's elegant and simple.

And not tail recursive, so you can't expect the compiler to optimize that into a loop. Recursion for linear problems is generally a bad idea due to the inherent overhead and risk of stack overflow, so I'd call the "elegant" solution unusable for robust code.

Further, there's no significant benefit over a corresponding iterative function. All in all, this isn't a place for recursion outside of the classroom.

Some parts get tricky, it's better to have a drawing to understand it better.

That sentence somewhat contradicts the previous one that the solution is simple. ;)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.