I am having problem reversing doubly linked list

Question

I am learning linked lists and was doing a question which asks you to reverse a doubly linked list. My code works perfectly fine but I don't understand how. You can ignore whole thing except the reverse_list function. As you can see, in the while loop the condition is ptr->next != NULL. This condition shouldn't let me reach the last node until the very end operation ptr = ptr->prev, which means no other operation inside that while loop should be performed in the last node.

By that logic ptr->prev must be still pointing to 2nd last node (or you can say 2nd node after reversing) when it should be NULL. I don't understand why even though it isn't properly reversed, it gives correct answer.

// reverse a double linked list
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    struct node *prev;
    int data;
    struct node *next;
} st;

void print(st *head)
{
    while (head)
    {
        printf("%d ", head->data);
        head = head->next;
    }
}

void add_node(st *head, int data)
{
    st *ptr = malloc(sizeof(st));
    ptr->data = data;
    ptr->next = NULL;
    while (head->next)
    {
        head = head->next;
    }
    head->next = ptr;
}

st *reverse_list(st *head)
{
    st *ptr = head->next;
    head->next = NULL;
    while (ptr->next != NULL)
    {
        head->prev = ptr;
        ptr->prev  =ptr->next;
        ptr->next = head;
        head = ptr;
        ptr = ptr->prev;
    }
    ptr->next = head;;
    head = ptr;
    return head;
}

int main()
{
    st *head = malloc(sizeof(st));
    head->prev = NULL;
    head->data = 12;
    head->next = NULL;

    add_node(head, 22);
    add_node(head, 1);
    add_node(head, 24);
    add_node(head, 45);

    printf("before reverse\n");
    print(head);

    head = reverse_list(head);
    printf("\nafter reverse\n");
    print(head);

    return 0;
}

// here is the output

before reverse
12 22 1 24 45 
after reverse
45 24 1 22 12 

Answer 1

There are multiple problems:

• void add_node(st *head, int data) does not properly construct a doubly linked list: it should take a pointer to the head pointer in the caller's scope, special case the first node, and set ptr->next to point to the previous node in the list.

• reverse_list has undefined behavior if the list is empty (head == NULL) or if it has a single element (head->next == NULL).

• the print function iterates along the next pointers, but it does not check that the prev pointers are correct. The program produces the expected output for the simple 4 element test case, but the prev links are incorrect in both the constructed list and its reversed version.

Here is a modified version:

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

typedef struct node {
    struct node *prev;
    struct node *next;
    int data;
} st;

void print(const char *msg, const st *head) {
    printf("%s", msg);
    while (head) {
        printf(" %d", head->data);
        head = head->next;
    }
    printf("\n");
}

st *add_node(st **headp, int data) {
    st *ptr = malloc(sizeof(st));
    if (ptr == NULL)
        return NULL;
    ptr->data = data;
    ptr->prev = NULL;
    ptr->next = NULL;
    if (*headp == NULL) {
        return *headp = ptr;
    } else {
        st *last = *headp;
        while (last->next) {
            last = last->next;
        }
        ptr->prev = last;
        return last->next = ptr;
    }
}

st *reverse_list(st *head) {
    // iterate on the list, swapping the next and prev links
    for (st *node = head; node; node = node->prev) {
        st *next = node->next;
        node->next = node->prev;
        node->prev = next;
        head = node;
    }
    return head;
}

void free_list(st **headp) {
    for (st *node = *headp; node;) {
        st *next = node->next;
        free(node);
        node = next;
    }
    *headp = NULL;
}

int main(void)
{
    st *head = NULL;

    add_node(&head, 12);
    add_node(&head, 22);
    add_node(&head, 1);
    add_node(&head, 24);
    add_node(&head, 45);

    print("before reverse: ", head);
    head = reverse_list(head);
    print("after reverse:  ", head);

    free_list(&head);
    return 0;
}

Output:

before reverse:  12 22 1 24 45
after reverse:   45 24 1 22 12