cpppro

Reverse linked list using pointers

In C Tidbits, Data Structures in C/C++ on October 25, 2006 at 6:22 pm

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…
SLL_reverse_1
now result holds one reversed node, and curr points to the rest of the linked list..
SLL_reverse_2

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

we reversed successfully….
SLL_reverse_4

here is the routine for doing this…..

please refer http://www.refcode.net/2013/02/reverse-linked-list-using-pointers.html
Advertisements
  1. […] Reversing a single linked list is explained in this post […]

  2. […] Here is the routine for reversing single linked list recursively, for reversing iteratively see the earlier post . For reversing circular single linked list visit this post. This routine takes a single linked list as argument and reverse it and returns back the head node to the reversed list. […]

  3. […] Here is the routine for reversing single linked list using a stack, for reversing linked list using pointers, see the earlier post. For reversing linked list recursively visit this post. This routine takes a single linked list as argument and reverse it and returns back the head node to the reversed list. […]

  4. wow! pretty illustrative, I can only say keep the good work bro.

  5. This site so far concentrated on linked lists in data structures, is there any chance of writing about other data structures in the same depth…

  6. I wrote an implementation of the LinkedList class in JavaScript using the MooTools library. I also wrote a challenge and solution to reversing a singly linked list:

    http://www.thetruetribe.com/2008/05/javascript-challenge-reverse-linked.html

  7. I modified it based on this to remove another temp element based on the code here- http://www.informatics.susx.ac.uk/courses/dats/notes/html/node46.html

    void reverse(Node **head){

    Node *result = NULL;
    Node *current = *head;
    *head=NULL;
    while (current)
    {
    result=current;
    current = current->next; // tricky: note the next node
    result->next = *head;
    *head = result;
    }

    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: