 Data Structures -- Linked List -- Reverse, Reverse a linked list |
|
|
|
|
  |
 Oct 29 2007, 02:50 PM
Post
#1
|
|
|
Super Member  Group: [HOSTED] Posts: 284 Joined: 1-October 07 From: India Member No.: 50,968  |
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 trap17.com. i Have already answered this question in one of my older questions. Solution 1 Here is one simple solution... CODE 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. |
 |
 
|
|
Oct 31 2007, 01:53 AM
Post
#2
|
|
|
Newbie [Level 1] Group: Members Posts: 12 Joined: 24-October 07 Member No.: 51,949 |
There aren't too many simpler iterative algorithms than the one you've given. I would perhaps have the function return a result:
CODE 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; } |
|
|
|
|
Feb 11 2008, 06:15 PM
Post
#3
|
|
|
Trap Double Mocha Member Group: Members Posts: 2,360 Joined: 21-September 07 Member No.: 50,369 |
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 |
|
|
|
|
Mar 28 2008, 05:31 AM
Post
#4
|
|
|
Trap Double Mocha Member Group: Members Posts: 2,360 Joined: 21-September 07 Member No.: 50,369 |
Replying to Trap FeedBackerYou are returning NULL, set head to tmp first.
|
|
|
|
|
Similar Topics
|
Lo-Fi Version | Time is now: 20th July 2008 - 05:52 PM |