Related Blog Items

• Reversing a circular single linked list using pointers
• Reversing a double linked list
• Reversing a single linked list using stack
• Reversing single linked list recursively
• Questions asked in various job interviews (in Programming)

Reversing a single list can achieved using a stack very easily. however this can be done without using stack, and by simply using three additional pointers. Let us say we are using curr, next, result pointers, curr points to current node, next obviously points to the next node, result points to the new reversed linked list.
here is the pictorial representation of this operation for better understanding…

now result holds one reversed node, and curr points to the rest of the linked list..

now result holds a pointer to the reversed linked list (reversed two pointers already)…. curr holds rest of the list

we reversed successfully….

here is the routine for doing this…..

void reverse_single_linked_list(struct node** headRef)
{
  struct node* result = NULL;
  struct node* current = *headRef;
  struct node* next;
  while (current != NULL)
  {
    next = current->next; // tricky: note the next node
    current->next = result; // move the node onto the result
    result = current;
    current = next;
  }
  *headRef = result;
}

please let me know your comments….

Popularity: 90%

You need to log on to convert this article into PDF

Related Blog Items

• Reversing a circular single linked list using pointers
• Reversing a double linked list
• Reversing a single linked list using stack
• Reversing single linked list recursively
• Questions asked in various job interviews (in Programming)

This entry was written by openasthra and posted on October 25, 2006 at 6:22 pm and filed under C Tidbits, Data Structures in C/C++. Bookmark the permalink. Follow any comments here with the RSS feed for this post. Post a comment or leave a trackback: Trackback URL.