Linked List Reversal has errors

Question

In our class right now we're covering nodes and linked lists, and are working on our first linked list program.

We've been given the following guidelines by the teacher:

Make sure your main function will accept 10 characters from STDIN and create a linked list with those characters (so your nodes will have a char member). Then, add an additional function called reverse. The purpose of the reverse function will be to create a copy of the linked list with the nodes reversed. Finally, print off the original linked list as well as the reversed linked list.

I've gotten it all written out, and I've compiled it with no errors - but the program doesn't work as intended, and I'm not entirely sure why. I'm sure it has something to do with how I've set up the pointers to "walk" the nodes - as the debug I put in shows it looping twice per user input letter. Specifications are that we're only supposed to use one function, and we pass a Node* to the function, and it returns the same. The function cannot print out anything - only make the second list that is a reverse of the first.

Any help would be greatly appreciated, I'm not terribly good at this yet and I'm sure I've made some rather silly mistakes.

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

//struct declaration with self-reference to make a linked list
struct charNode {
    char data;
    struct charNode *nextPtr;
    struct prevNode *prevPtr;
};

typedef struct charNode Node; //makes Node an alias for charNode
typedef Node *NodePtr; //makes NodePtr an alias for a pointer to Node (I think?)

//function declaration for a reverse function
Node* reverse(Node *stPtr);

int main(void)
{
    //main function takes 10 letters and puts them in a linked list
    //after that, it calls the reverse function to create a reversed list of those characters
    //lastly it prints both lists
    NodePtr newNode = NULL;
    char input;
    Node* revStart;
    unsigned int counter = 0;

    printf("Enter 10 letters to make a list: ");
    NodePtr currentPtr = NULL; //sets currentPointer to startNode.
    NodePtr previousPtr = NULL; //set previousPointer to null to start

    while(counter<= 10)
    {
        scanf("%c", &input); //gather next letter
        NodePtr newNode = malloc(sizeof(Node)); //creates a new node
        if (newNode != NULL) //checks to make sure the node was allocated correctly
        {
            newNode->data = input; //makes the new node's data == input
            newNode->nextPtr = NULL; //makes the nextPtr of the newNode NULL
        }
        currentPtr = newNode; //sets currentPtr to the address of the newNode
        if(previousPtr == NULL) { //first time around previousPtr == NULL
            newNode->nextPtr = newNode;
            previousPtr = newNode; //sets previousPtr to the address of the new node (1st time only)
        } else { //afterwards, currentPtr won't be NULL
            previousPtr->nextPtr = currentPtr; //last node's pointer points to the current node
            previousPtr = newNode; //update previous pointer to the current node
        }
        ++counter;
        //debug
        printf("\nLoop #%d\n", counter);
    }
    revStart = reverse(newNode);
    puts("The list is: ");
    while (newNode != NULL){
        printf("%c --> ", newNode->data);
        currentPtr = currentPtr->nextPtr;
    }
    puts("NULL\n");
}

//reversing the nodes
Node* reverse(Node *stPtr)
{
     //make a new node
    NodePtr currentPtr = stPtr->nextPtr; //get the next letter ready (this will point to #2)
    NodePtr prevRevPtr = NULL; //previous reverse node pointer
    Node* revStart;
    for(unsigned int counter = 1; counter <= 10; ++counter)
    {
        NodePtr revNode = malloc(sizeof(Node));
        if(revNode != NULL) //if reverseNode is allocated...
        {
            if(prevRevPtr = NULL) //if previousReversePointer = NULL it's the "first" letter
            {
                revNode->data = stPtr->data; //letter = current letter
                revNode->nextPtr = NULL; //this is the "last" letter, so NULL terminate
                prevRevPtr = revNode; //previousReversePointer is this one
            }else //after the first loop, the previous ReversePointer will be set
            {
                revNode->data = currentPtr->data; //set it's data to the pointer's data
                revNode->nextPtr = prevRevPtr; //reverseNode's pointer points to last node entered
                currentPtr = currentPtr->nextPtr; //moves to next letter
                prevRevPtr = revNode; //changes previous reverse node to current node
                if(counter == 10)//on the last loop...
                {
                    revStart = revNode; //set revStart as a pointer to the last reverse node
                    //which is technically the "first"
                }
            }
        }    
    }
    return revStart;
}

Answer 1

Okay so we don't need to contend with no line breaks in commments:

Node *reverse(Node *list) {
  Node *rev = NULL; 
  while (list) {
    Node *elt = list;    // pop from the list
    list = list->next;   
    elt->next = rev;     // push onto reversed list.
    rev = elt; 
  }
  return rev;
}

Answer 2

As you wrote in comments, you probably don't need to have a previous pointer; you can just create a singly linked list.

There are several issues in your code, including:

• When malloc returns NULL, you still continue with the loop -- only part of the code is protected by the if that follows, but not the rest. You should probably just exit the program when this happens.

• Your algorithm does not maintain a reference to the very first node, i.e. the place where the linked list starts. When you print the list you should start with the first node of the list, but instead you start with newNode, which is the last node you created, so obviously not much will be printed except that last node. Moreover, both other pointers you have, will also point to the last node (currentPtr, previousPtr) when the loop ends.

• newNode->nextPtr = newNode; temporarily creates an infinite cycle in your list. This is resolved in the next iteration of the loop, but it is unnecessary to ever make the list cyclic.

• In the reverse function you have if(prevRevPtr = NULL)... You should get a warning about that, because that is an assignment, not a comparison.

Some other remarks:

• The reverse function unnecessarily makes distinction between dealing with the first node and the other nodes.

• It is also not nice that it expects the list to have 10 nodes. It would be better to just rely on the fact that the last node will have a NULL for its nextPtr.

• It is a common habit to call the first node of a linked list, its head. So naming your variables like that is good practice.

• As you are required to print both the initial list and the reversed list, it would be good to create a function that will print a list.

• As you need to create new nodes both for the initial list and for the reversed list, it would be good to create a function that will create a node for you.

  (I know that your teacher asked to create only one function, but this is just best practice. If this doesn't fit the assignment, then you'll have to go with the malloc-related code duplication, which is a pitty).

• As you defined the type NodePtr, it is confusing to see a mix of Node* and NodePtr in your code.

Your question was first not clear on whether the reversal of the list should be in-place or should build a new list without tampering with the initial list. From comments it became clear you needed a new list.

I probably didn't cover all problems with the code. Here is a corrected version:

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

struct charNode {
    char data;
    struct charNode *nextPtr;
};

typedef struct charNode Node;
typedef Node *NodePtr;

NodePtr reverse(Node *stPtr);
void printList(Node *headPtr);
NodePtr createNode(int data, NodePtr nextPtr);

int main(void) {
    NodePtr headPtr = NULL; // You need a pointer to the very first node
    NodePtr tailPtr = NULL; // Maybe a better name for currentPtr

    printf("Enter 10 letters to make a list: ");
    for (int counter = 0; counter < 10; counter++) {
        char input;
        scanf("%c", &input);

        NodePtr newNode = createNode(input, NULL);

        if (headPtr == NULL) {
            headPtr = newNode;
        } else {
            tailPtr->nextPtr = newNode;
        }
        tailPtr = newNode;
    }

    NodePtr revHeadPtr = reverse(headPtr);
    puts("The list is:\n");
    printList(headPtr);
    puts("The reversed list is:\n");
    printList(revHeadPtr);
}

void printList(NodePtr headPtr) {
    while (headPtr != NULL) {
        printf("%c --> ", headPtr->data);
        // You can just move the head pointer: it is a variable local to this function
        headPtr = headPtr->nextPtr;
    }
    puts("NULL\n");
}

NodePtr createNode(int data, NodePtr nextPtr) {
    NodePtr newNode = malloc(sizeof(Node));
    if (newNode == NULL) { // If malloc fails, exit the program
        puts("Cannot allocate memory\n");
        exit(1);
    }
    newNode->data = data;
    newNode->nextPtr = nextPtr;
    return newNode;
}

NodePtr reverse(NodePtr headPtr) {
    NodePtr revHeadPtr = NULL;

    while (headPtr != NULL) {
        revHeadPtr = createNode(headPtr->data, revHeadPtr);
        // You can just move the head pointer: it is a variable local to this function
        headPtr = headPtr->nextPtr;
    }
    return revHeadPtr;
}

Answer 3

Assuming your list is properly wired from inception, reversing a double-linked list is basically this:

Node *reverse(Node *stPtr)
{
    Node *lst = stPtr, *cur = stPtr;
    while (cur)
    {
        Node *tmp = cur->nextPtr;
        cur->nextPtr = cur->prevPtr;
        cur->prevPtr = tmp;
        lst = cur;
        cur = tmp;
    }
    return lst;
}

That's it . All this does is walk the list, swapping pointers, and retaining whatever the last node processed was. When done correctly the list will still be end-terminated (first node 'prev' is null, last node 'next' is null, and properly wired between.

I strongly advise walking a list enumeration through this function in a debugger. With each iteration watch what happens to cur as it marches down the list, to the active node's nextPtr and prevPtr values as their swapped, and to lst, which always retains the last-node processed. It's the new list head when done.