Jump to content
xisto Community
varalu

Data Structures -- Linked List -- Reverse Reverse a linked list

Recommended Posts

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

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

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

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

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
Linear Linked ListsData Structures -- Linked List -- Reverse

How to reverse a linear linked list without using a temporaly variable.

-question by Bamo

Share this post


Link to post
Share on other sites
Singly Linked Linear List(SLLL) and Doubly Linked Linear List(DLLL)Data Structures -- Linked List -- Reverse

Write an Algorithm to reverse a SLLL and DLLL.

-question by Bamo

Share this post


Link to post
Share on other sites
linked list reverse and memoryData Structures -- Linked List -- Reverse

in 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 michael

Keywords: reverse linked list

Share this post


Link to post
Share on other sites
stack codesData Structures -- Linked List -- Reverse

hi 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
linked listData Structures -- Linked List -- Reverse

I 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
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

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

Terms of Use | Privacy Policy | Guidelines | We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.