Whwt is the algorithm to reverse the elements of a single linked lists without using a temporary list?

Answer 1

The actual code depends on whether the list is singly-linked or doubly-linked, however the algorithm is largely the same for both. Of course if the list is doubly-linked there is no need to reverse the list at all since the list can simply be traversed in reverse. However, for the sake of completeness, example code is provided for both.

The Algorithm

Set the current node to be the head node then repeatedly extract the current node's next node and insert it at the head of the list until the current node's next node is NULL.

Singly-linked Example (C++)

Assuming the list is a reference that has a head node pointer, and each node in the list has a next node pointer, a singly-linked list can be reversed as follows:

// Ensure there is a head node.
if(Node* current = list.head)

{

// Ensure the current node has a next node.

while(Node* temp= current->next )

{

// Move the next node to the head of the list.

current->next = temp->next;

temp->next = list.head;

list.head = temp;

}

}

Doubly-linked Example (C++)

In doubly-linked lists, it is assumed each node has a previous node pointer as well as a next node pointer. The algorithm is essentially the same but the node pointers obviously need to be adjusted in both directions, as follows:

// Ensure there is a head node.
if( Node* current = list.head )

{

// Ensure the current node has a next node.

while(Node* temp= current->next )

{

// Move the next node to the head of the list.

current->next = temp->next;

temp->next.prev = current;

temp->next = list.head;

list.head->prev = temp;

list.head = temp;

temp->prev = NULL;

}

// If the list also has a tail node, remember to reset it!

list.tail = current;

}

In both cases, when the while() loop finishes, the current node ends up pointing at the tail node. However, the current node never actually changes -- it always points to the same node, the original head node. As each loop progresses, the current node is demoted towards the tail, one position at a time, to eventually become the tail node. When the current node has no next node, the loop terminates and the list is completely reversed.

Repeating the reversal will naturally restore the list to its original order.

Circular Lists

The exact same algorithm can also be applied to circular lists. The only major difference is that you terminate the loop when temp points to the head of the list, rather than when it is NULL.

Answer 2

#include #include #include // The list element type and head.struct node {int data;struct node *link;};static struct node *first = NULL;// A reverse function which uses only two extra pointers.void reverse() {struct node *nxtNode, *curNode;// curNode traverses the list, first is reset to empty list.curNode = first;first = NULL;// Until no more in list, insert current before first and advance.while (curNode != NULL) {// Need to save next node since we're changing the current.nxtNode = curNode->link;// Insert at start of new list.curNode->link = first;first = curNode;// Advance to next.curNode = nxtNode;}}// Code to dump the current list.static void dumpNodes() {struct node *curNode = first;printf ("==========\n");while (curNode != NULL) {printf ("%d\n", curNode->data);curNode = curNode->link;}}// Test harness main program.int main (void) {clrscr();int i;struct node *newnode;// Create list (using actually the same insert-before-first// that is used in reverse function.for (i = 0; i < 5; i++) {newnode = malloc (sizeof (struct node));newnode->data = i;newnode->link = first;first = newnode;}// Dump list, reverse it, then dump again.dumpNodes();reverse();dumpNodes();printf ("==========\n");return 0;}

Answer 3

Iterate through the list, retrieving elements.  As you retrieve them, place them on a second list, placing each at the head of list.  When you are done, the second list will be the reverse of the first list.

Answer 4

You don't. Iterating backwards through a singly linked list is very inefficient. If you need this behavior, then you should change to using a doubly linked list or some other structure.

Answer 5

create an empty list for output

while the input list is not empty do

move the first element of the input list to the beginning of the output list

end while;

Answer 6

Traverse the list and reverse the direction of the *next pointers

Answer 7

algorithm for implementing singly linked list with c