Thread: Reversing The Linked List by reversing the links only

  1. #1
    Registered User
    Join Date
    Aug 2016
    Posts
    3

    Question 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?

  2. #2
    Registered User
    Join Date
    Apr 2013
    Posts
    1,649
    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.

  3. #3
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    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).

  4. #4
    Registered User
    Join Date
    Apr 2013
    Posts
    1,649
    In the display function the for loop should be:

    Code:
    /* ... */
        for(t = start; t != NULL; t = t->ptr) {
    As commented by algorism, the reverse function needs some changes. Some hints based on algorism's post to get you started:

    Code:
    /* ... */
        if(start == NULL)   /* if empty list, nothing to do */
            return;
        curr = start;
        next = curr->next;
    Last edited by rcgldr; 08-24-2016 at 04:32 PM.

  5. #5
    Registered User
    Join Date
    Apr 2013
    Posts
    1,649
    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 */
        /* ... */

  6. #6
    Registered User
    Join Date
    May 2009
    Posts
    3,744
    Me I would just create a double link list.

    But, that seems to never be the answer the prof. wants.

    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.

    Then create a new list by pop-ing the old list to the new list.

    But, that is also NOT something a link list containing ints that a prof. will want.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  7. #7
    Registered User
    Join Date
    Apr 2013
    Posts
    1,649
    Quote Originally Posted by stahta01 View Post
    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).

  8. #8
    Registered User
    Join Date
    May 2009
    Posts
    3,744
    Quote Originally Posted by rcgldr View Post
    The sequence to reverse a list would be pop_front(original list), push_front(new reversed list) (not push_back() to end of list).
    You are right.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Reversing a linked List
    By 00111_Bim in forum C Programming
    Replies: 4
    Last Post: 04-09-2014, 11:49 PM
  2. Reversing a linked list...
    By csharp100 in forum C Programming
    Replies: 2
    Last Post: 11-09-2010, 12:37 AM
  3. reversing integers
    By rachael033 in forum C++ Programming
    Replies: 3
    Last Post: 06-16-2006, 03:58 AM
  4. Reversing words
    By jlf029 in forum C++ Programming
    Replies: 7
    Last Post: 12-03-2005, 09:48 PM
  5. reversing a singly linked list
    By galmca in forum C Programming
    Replies: 6
    Last Post: 02-07-2005, 10:25 AM

Tags for this Thread