I am trying to write a function which reverses a linked list by reference

Question

I am not sure if what I am writing is right. My strategy is first getting by the first node of the origin list and by that creating a new list of one node (while making the next node of the origin list to head node), and then by iteratively getting each time the first node and link it to new, reversed list, by being the head of that list. Here is what I have done so far:

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

void reverseList(Node **head) {
    Node *curr = *head;        //
    Node *new_node = *head;    
    Node *prev = NULL;

    new_node->next = NULL;  //the new list is to end with the first node of the origin list//

    while (curr != NULL) {      //traverse through the whole list//
        curr = curr->next;
        prev = curr;            //getting the next first node// 
        prev->next = new_node;  //and making it linked to the new list//
    }

    *head = new_node;   //the new, reversed list//
}

Did you try to check yourself that the code is correct or not ? — GAURANG VYAS, Jun 25 '17 at 11:01
Before starting the loop you setting the `head->next ` to `NULL` so the the `while` loop will run only once. — GAURANG VYAS, Jun 25 '17 at 11:01
`new_node` is `head` due to `Node* new_node=*head;` and the the line `new_node->next=NULL;` sets the `head->next ` to `NULL`. — GAURANG VYAS, Jun 25 '17 at 11:42

score 1 · Answer 1 · answered Jun 25 '17 at 12:02

There is a logical error in your code -
Observe the code segment :

Node* new_node=*head;    
Node* prev=NULL;

new_node->next=NULL;

First line sets new_node to head, while the last line sets the next pointer of new_node to NULL. So, effectively you are setting the head->next to NULL. As a result, the while loop run at most once.

Here I give a slightly modified reverseList function to you

void reverseList(Node** head)  
{
    Node* curr=*head; 
    Node *temp;       
    Node* prev=NULL;

    while(curr!=NULL)     
    {
        temp = curr->next; // keep track of the current nodes next node.
        curr->next = prev; // reverse the link for the current node
        prev=curr; // current  node becomes the previous node for next iteration
        curr=temp; // now the initially next node becomes the current node for next iteration
    }

    /*
        After the end of the whiie loop, prev points to the last node.
        So the change *head to point to the last node.
    */

    *head = prev; 

}

I am trying to write a function which reverses a linked list by reference

1 Answers1