How do you a reverse single linked list?

Answer 1

Let us assume we have a linked list similar to the following setup:

struct linked_list_node {

int data;

struct linked_list_node *next;

};

struct linked_list {

int size;

struct linked_list_node *root;

};

// reverses the order of the nodes in list

void reverseList(struct linked_list *list) {

struct linked_list_node *current = list->root;

struct linked_list_node *next = current->next;

struct linked_list_node *last = list->root;

// the old root will be the new end, so must point to null

list->root->next = NULL;

while( next != NULL ) {

// update current node

current = next;

// update next node for the next iteration so we don't lose the pointer

next = current->next;

// actual reversal - the current node should point to the last node

current->next = last;

// update lastNode

last = current;

}

// point the original list to the new root

list->root = current;

}