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