varalu 0 Report post Posted October 29, 2007 Give an algorithm to reverse a linked list with a time complexity of O(n) and minimal space complexity. What is a linked list? Search Xisto.com. i Have already answered this question in one of my older questions. Solution 1 Here is one simple solution... Void ReverseList(node* head){ node *temp,*current,*result; temp=null; result=null; current=head; while(current!=null) { temp=current->next; current->next=result; result=current; current=temp; } head=result; The above was suggested by my friend. But i guess we still have some problems in the above code and can be refined more. Do post back with better ideas and solutions. Share this post Link to post Share on other sites
pointybirds 0 Report post Posted October 31, 2007 There aren't too many simpler iterative algorithms than the one you've given. I would perhaps have the function return a result: Node *reverse(Node *head) { Node *curr=head, *prev=NULL, *next; while (curr != NULL) { next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev;} Share this post Link to post Share on other sites
iGuest 3 Report post Posted February 11, 2008 i think this will serve better Data Structures -- Linked List -- Reverse Replying to pointybirds NODE* revlist(NODE *head) { NODE *tmp=NULL, *tmp1=NULL; while (head != NULL) { tmp = head; head = head->next; tmp->next = tmp1; tmp1 = tmp; } return head; } -reply by raja Share this post Link to post Share on other sites
iGuest 3 Report post Posted March 28, 2008 Replying to Trap FeedBackerYou are returning NULL, set head to tmp first. Share this post Link to post Share on other sites
iGuest 3 Report post Posted July 27, 2008 1.Give an example in which there is the implimentation of copy constructor and assignment operator an string should be there.2. Why static method don't have this pointer?-question by prangya Share this post Link to post Share on other sites
iGuest 3 Report post Posted September 2, 2008 simple linked list Data Structures -- Linked List -- Reverse /* * Simple operations on linked list. If any problem * please mail to me jagannath_pattar@yahoo.Co.In */ #include <stdio.H> /* * Data structure used, its simple */ Typedef struct linked_list_s { int value; struct linked_list_s *next; }linked_list_t; /* * Add a node at the end of the list. */ Linked_list_t* add_node(linked_list_t *head, int value) { linked_list_t *newNode = NULL; linked_list_t *node = head; linked_list_t *prev = head; newNode = (linked_list_t *)calloc(1, sizeof(linked_list_t)); newNode->value = value; while(node) { prev = node; node = node->next; } if(prev == node) return newNode; prev->next = newNode; return head; } /* * delete a specified node from the list. */ Linked_list_t* delete_node(linked_list_t *head, int value) { linked_list_t *node = NULL; linked_list_t *prev = NULL; for(node = head; node != NULL; prev = node, node = node->next) { if(node->value == value) { //Check for head node modification if(prev == NULL) { head = head->next; free(node); return head; } prev->next = node->next; free(node); return head; } } return head; } /* * display all the nodes of the list. */ Void list_nodes(linked_list_t *head) { linked_list_t *node = head; printf("nHead"); while(node) { printf("->%d ",node->value); node = node->next; } printf("->NULLand"); } /* * Display all the nodes in reverse order withoout modifying list. */ Void list_nodes_in_reverse_order(linked_list_t *head) { linked_list_t *end = NULL; linked_list_t *node = NULL; printf("nReverse Head"); while(head != end) { node = head; while(node->next != end) node = node->next; printf("->%d ",node->value); end = node; } printf("->NULLand"); } /* * Reversing the linked list with recursion; I recommond this method.. */ Linked_list_t* reverse_with_recursion_anotherway(linked_list_t* current, linked_list_t* parent) { linked_list_t* revhead = NULL; if(current == NULL) revhead = parent; else { revhead = reverse_with_recursion_anotherway(current->next, current); current->next = parent; } return revhead; } /* * Reversing the linked list; */ Linked_list_t* reverse_with_recursion(linked_list_t* node) { linked_list_t* temp = NULL; if(node->next == NULL) return node; temp = reverse_with_recursion(node->next); temp->next =node; return node; } /* * reversing linked list without recursion. */ Linked_list_t* reverse_without_recursion(linked_list_t* head) { linked_list_t* prevNode = NULL; linked_list_t* currNode = head; linked_list_t* nextNode = head->next; while(currNode) { currNode->next = prevNode; prevNode = currNode; if(nextNode == NULL) break; currNode = nextNode; nextNode = nextNode->next; } return currNode; } /* * main program, which displays menu for maitaining linked list. */ Main() { int choice = -1; int value = 0; linked_list_t *head = NULL; linked_list_t *node = NULL; do { printf("and what you wanna do?and"); printf("1. Add a node and"); printf("2. Delete a node and"); printf("3. List all nodes and"); printf("4. Reverse (without recursion) the list and"); printf("5. Reverse (recursively) the list and"); printf("6. Reverse (recursively) another wayand"); printf("7. Just display in reverse orderand"); printf("8. Exit and"); scanf("%d",&choice); switch(choice) { case 1: printf("nEnter value: "); scanf("%d",&value); head = add_node(head, value); break; case 2: printf("nEnter value: "); scanf("%d",&value); head = delete_node(head, value); break; case 3: list_nodes(head); break; case 4: node = head; head = reverse_without_recursion(head); break; case 5: node = head; while(node->next) node = node->next; head = reverse_with_recursion(head); head->next = NULL; head = node; break; case 6: head = reverse_with_recursion_anotherway(head, NULL); break; case 7: list_nodes_in_reverse_order(head); break; case 8: exit(0); break; } }while(1); } -reply by jagannath Share this post Link to post Share on other sites
iGuest 3 Report post Posted December 14, 2008 Linear Linked ListsData Structures -- Linked List -- ReverseHow to reverse a linear linked list without using a temporaly variable. -question by Bamo Share this post Link to post Share on other sites
iGuest 3 Report post Posted December 14, 2008 Singly Linked Linear List(SLLL) and Doubly Linked Linear List(DLLL)Data Structures -- Linked List -- ReverseWrite an Algorithm to reverse a SLLL and DLLL.-question by Bamo Share this post Link to post Share on other sites
iGuest 3 Report post Posted May 3, 2009 linked list reverse and memoryData Structures -- Linked List -- Reversein the some of your funntions when returning the memory becomes null head->value=ok head->next becomes null after function exit ============== void ReverseList(LISTP* head) { LISTP *temp,*current,*result; temp=NULL; result=NULL; current=head; while(current!=NULL) { temp=current->next; current->next=result; result=current; current=temp; } head=result; } =================== if I print hte list inside the function it is ok void display_list(LISTP* listp) { LISTP* temp=listp; while(temp->next!=NULL) { printf("%dand",temp->data); temp=temp->next; } } ====================== but if I exit the function the next pointer becomes null , I suppoise the solution is using static pointer allocated outside the function ... any way my idea ========== void reverselist(LISTP* listp) { LISTP* next = (LISTP*)malloc(sizeof(LISTP)); LISTP* next_of_next = (LISTP*)malloc(sizeof(LISTP)); next=listp->next; if(next!=NULL) next_of_next = next->next; listp->next = NULL; while(next_of_next!=NULL) { next->next=listp; listp=next; next=next_of_next; next_of_next=next_of_next->next; } display_list(listp); //free(next); ??? is nneeded //free(next_of_next); is needed}-reply by michaelKeywords: reverse linked list Share this post Link to post Share on other sites
iGuest 3 Report post Posted November 4, 2009 stack codesData Structures -- Linked List -- Reversehi there guys...Can you help me in my simple problem? how was the codes in reversing a name using stacks? just like this...M a r I c h u then the output will be like this one...U h c I r a m thanks for your help.,in advance! -question by mharie_chue Share this post Link to post Share on other sites
iGuest 3 Report post Posted December 30, 2009 linked listData Structures -- Linked List -- ReverseI need to show a full program of each linked list I.E 1.Singly linked list 2.Doubly linked list 3. Circular linked list 4. Circular doubly linked list -reply by sintay Share this post Link to post Share on other sites
iGuest 3 Report post Posted February 19, 2010 Data Structures -- Linked List -- Reverse - Reverse a linked listData Structures -- Linked List -- Reverse//The right solution...typedef struct elementT{ Int value; Struct elementT *next; }element;void reverse(element **head) { element *current=*head,*result=NULL,*temp=NULL; while(current!=NULL) { temp=current->next; current->next=result; result=current; current=temp; } *head=result; } Share this post Link to post Share on other sites
iGuest 3 Report post Posted September 12, 2010 Here is my two centsProgram to reverse a singly list ITERATIVELY,http://forums.xisto.com/no_longer_exists/ to reverse a linked list RECURSIVELYtechnicalypto.com/2010/03/reverse-singly-linked-list-recursively.html Share this post Link to post Share on other sites