how to reverse items in linked list?

This is a discussion on how to reverse items in linked list? within the C Programming forums, part of the General Programming Boards category; here is my code Code: struct list { NodeType* listData; int length; }; UnsortedType* CreateList(void) { UnsortedType *list = (UnsortedType ...

  1. #1
    Registered User
    Join Date
    Dec 2010
    Posts
    29

    how to reverse items in linked list?

    here is my code
    Code:
    struct list
    {
    	NodeType* listData;
    	int length;
    };
    
     UnsortedType* CreateList(void)
    {
    	UnsortedType *list = (UnsortedType *) malloc(sizeof(UnsortedType));
    	list->listData = NULL;
    	list->length = 0;
    	return list;
     }
    
    
    void InsertItem(UnsortedType *list, int key, char* name)
    {
    	NodeType* current; /* traveling pointer */
    
    	current = (NodeType*) malloc(sizeof(NodeType));
    	current->key = key;
    	strcpy(current->name, name);
    	current->next = list->listData;
    	list->listData = current;
    	ist->length++;
    }

    i am wondering how i can permanently reverse the orders of the items in the list.
    void reverse(NODE* list)

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,315
    Did you try searching the web? Google turned up dozens of great sites with examples. The forum should be your last resort, and even then you should make an attempt to do it before asking for help.

  3. #3
    Registered User
    Join Date
    Dec 2010
    Posts
    29

    Smile ok can someone tell me if this is correct?

    Code:
    void reverse(NODE* list)
    {
    	NODE* temp, 
    	NODE * previous = NULL;
    	while(list!=NULL)
    	{
    		NODE *temp=list->next;
    	        list->next=previous;
    		previous=list;
    	        list=temp;
    	}
    }
    Last edited by ilikeapplepie; 04-08-2011 at 12:43 PM. Reason: typo

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,315
    Did you test it? Did it reverse the list as you would expect? If not, what did it do (or not do) incorrectly?

  5. #5
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,529
    The only way I'm aware of that really works is to rebuild the list from back to front. If you have a function that inserts a node before another given node, call it such that everything after the head is added to the new list before the head node.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,269
    To reverse a linked-list:
    Pop A, Push B, repeat until A empty, return B.

    Looking at your code, this is how far I got before I noticed that it can not work:
    Code:
    void reverse(NODE* list)
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by iMalc View Post
    To reverse a linked-list:
    Pop A, Push B, repeat until A empty, return B.

    Looking at your code, this is how far I got before I noticed that it can not work:
    Code:
    void reverse(NODE* list)
    That depends if you care if you swap the contents of the list, instead of the nodes themselves.


    Quzah.
    Hope is the first step on the road to disappointment.

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,269
    I never consider swapping the contents of each node to be an option, for any linked-list algorithms.
    He said reverse it, not butcher it!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,831
    Walk the list beginning to end, changing each forward-link to point to the previous element you just came from.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. circularly linked list
    By BlackOps in forum C Programming
    Replies: 0
    Last Post: 07-18-2009, 08:12 AM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  3. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 12:21 PM
  4. Linked List Help
    By CJ7Mudrover in forum C Programming
    Replies: 9
    Last Post: 03-10-2004, 09:33 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21