Reverse linked list returning new linked list

Question

I need to implement a function that reverses a linked list but i don't know how to return a newly formed linked list as a result.

typedef struct node_t* Node;

struct node_t {
    int n;
    Node next;
};    

// create a new node with value n
Node nodeCreate(int n) 
{
    Node node = malloc(sizeof(*node));
    if (node == NULL) return NULL;

    node->n = n;
    node->next = NULL;

    return node;
} 

// reversing the linked list
Node reverseList(Node list) 
{
    if (list == NULL) return NULL;

    Node current, prev, next;
    current = rev_head;
    prev = NULL;

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

    list = prev;
    return list;
}

This is the code I have written so far.

How do I insert this reverse linked list into a different new linked list within the function reverseList it self?

Answer 1

There is a simple way in which you can reverse linked list

You can simply create a new linked list and add each node at the start of linked list which will create same linked list in reverse order

Node* revList(Node *start){
Node *startRev=NULL,*temp,*newNode;
temp = start;
while (temp->next!=NULL){
    newNode = (Node *) malloc (sizeof(Node));
    //Code for copying data from temp to new node

    if(startRev == NULL){
        startRev = newNode;
    }
    else {
        newNode->next = startRev;
        startRev = newNode;
    }
    temp = temp->next;
}
return startRev;
}

Answer 2

You can simply create a new node for every node in the original list and set the link in opposite order. Code could be:

Node createReversedList(Node node) {
    Node result = NULL;
    while (node != NULL) {
        Node n = nodeCreate(node->n);
        n->next = result;
        result = n;
        node = node->next;
    }
    return result;
}

Answer 3

You are juggling around your nodes on the original list, and modifying then in place - which means you have only one list, and modify its nodes.

If that is what you want, your code might work (as soon as you fix things like the rev_head variable that appears from nowhere) - and the new head of the list, which is on your prev variable: which means your code should just work.

(It is important that the typedef don't hide the pointer though, I'd suggest changing that.)

What you seem not to have understood quite well is that for this kind o structure, any node works as the head of a list - there is no "list" type, just "node" types - and if you happen to pick any node in the middle of a list, that will just represent a partial list, starting from that node as well. So when you change your previous "last" node to point to its previous "antecessor" as its "next", that is it: that node is now the head.

(The exception to this "node == list" equality is while the reversing algorithm is running - at that point you have nodes that point in one direction and nodes that point in another, and the extra "next" and "prev" variables provide the needed information to fix things. If this was production code, this part of the code would have to be protected in a thread-lock)

Otherwise, if you want to produce a reversed copy of the list, you will have to copy the old nodes along the way, and just fix where they are pointing.

#include <stdlib.h>
#include <string.h>

typedef struct node_t Node;
struct node_t {
    int n;
    Node next;
};    

// create a new node with value n
Node *nodeCreate(int n) {
    Node *node = malloc(sizeof(*node));
    if (node == NULL) return NULL;

    node->n = n;
    node->next = NULL;

    return node;
}   

void nodeCopy(Node *node_dst, Node *node_src) {
    if (node_src == NULL || node_dst == NULL || abs(node_dst - node_src) < sizeof(Node)) {
        return
    }
    memcpy(node_dst, node_src, sizeof(Node));
}

// reversing the linked list
Node *reverseList(Node *list) {
    Node *new_list, *prev;
    if (list == NULL) return NULL;

    new_list = nodeCreate(0);
    nodeCopy(new_list, list);
    new_list->next=NULL;
    prev = new_list;
    while(list->next != NULL) {
        list = list->next;
        new_list = nodeCreate(0);
        nodeCopy(new_list, list);
        new_list->next=prev;
        prev = new_list;   
    }
    return new_list;
}