Thread: Reversing The Linked List by reversing the links only

I have prepared a code to perform the above task:

Code:

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


struct node {
    int data;
    struct node *ptr;
}*start = NULL, *last = NULL;


void create() {
    char ch;
    struct node *t, *t1;
    do {
        t = (struct node*)malloc(sizeof(struct node));
        printf("Please Enter The Data: ");
        scanf("%d", &t->data);
        t->ptr = NULL;
        if(start == NULL) {
            start = t;
            t1 = t;
        } else {
            t1->ptr = t;
            t1 = t;
        }
        printf("Do you still want to insert(y/n)? ");
        fflush(stdin);
        scanf("%c", &ch);
    }while(ch != 'n');
    last = t;
}


void display() {
    struct node *t;
    for(t = start; start != NULL; t = t->ptr) {
        printf("%d --> ", t->data);
        if(t->ptr == NULL) {
            break;
        }
    }
    printf("NULL");
}


void reverse() {
    struct node *t, *t1, *t2;
    t2 = (struct node*)malloc(sizeof(struct node));
    t = start;
    for(int i = 1; t != NULL; i++) {
        t1 = t;
        if(i == 1) {
            t = t->ptr;
            t2->ptr = t->ptr;
            t->ptr = t1;
            t1->ptr = NULL;
        } else {
            t = t2->ptr;
            t2->ptr = t->ptr;
            t->ptr = t1;
        }
    }
    start = last;
}


int main() {
    create();
    display();
    reverse();
    display();
}

Here the function reverse() isn't working. What I am trying to do in the reverse() function is that *t points to the current node and *t1 points to the previous node and I created *t2 as a temporary node to store the address of the next node for incrementing *t purpose. However, it is not working. Can anyone tell me what I am doing wrong?

The functions should receive and return a pointer to a node, or receive a pointer to pointer to node (to update it). Main should contain a pointer to node and pass it (or it's address) as a parameter to the other functions.

Althouh fflush(stdin) may work for you (on Windows, presumably), it is not standard and doesn't do anything for me (which, being "undefined behavior" according to the standard, is actually one of the best results since technically it could do anything).

It's better to replace it with something that works for everybody, such as:

Code:

while (getchar() != '\n') ;

When using malloc you should include a test to ensure that the return value isn't NULL. And in C you don't need to cast the return value since void* is implicitly converted to any pointer type. (If your compiler complains then you're actually compiling as C++.)

It's bad practice to make your list variables global. Instead, as rcgldr said, it's better to define the pointer in main and pass it to the list functions (either as a double pointer that can be used to modify the pointer in main, or as a single pointer that is then passed back).

The "last" pointer doesn't have any real use. It's normally only used with a doubly-linked list.

The "i" in reverse has little purpose. If you want to do something special with the first node, just do it before the loop.

Instead of meaningless variable names like t, t1, t2, it would be easier to understand your code with names like curr, next, prev.

As for your reverse function, you need to rethink it. You shouldn't have to malloc another node.

You should have a function to delete the list (free the nodes).

Too late to edit, that should have been

Code:

/* ... */
    if(start == NULL)   /* if empty list, nothing to do */
        return;
    prev = NULL;
    curr = start;
    next = curr->ptr;  /* may want to rename the member from ptr to next */
    /* ... */

Originally Posted by stahta01

I would instead add to a already working link list these operations. pop removes the first Item on the list. add_to_end add the item to the end of the list.

The sequence to reverse a list would be pop_front(original list), push_front(new reversed list) (not push_back() to end of list).