Write a program to reverse a linked list

This question is related to Aztec-Systems Interview

Showing Answers 1 - 7 of 7 Answers

chandan

  • Jul 18th, 2006
 

Code
  1. **************************

  2. typedef struct nd {

  3.     int info;

  4.     struct nd *link;

  5. } node;

  6. /* AFTER CREATING LINK LIST */

  7. node *reverse(node * h)

  8. {

  9.     node *H = NULL, *p;

  10.     while (h != NULL) {

  11.         p = h;                  /* insert value of 1st node  into p */

  12.         h = h->next;

  13.         p->next = H;            /* insert p->next =NULL ,because H is equals to NULL (1st time) */

  14.         H = p;                  /* insert address of p into H */

  15.     }

  16.     return H;

  17. }

  18.  

  Was this answer useful?  Yes

This is a complete program to reverse a linked list in C.
first node is allocated memory but doesn't contain any data.



Code
  1. #include<stdio.h>

  2. #include<stdlib.h>

  3. struct list {

  4.     int month;

  5.     struct list *next;

  6. };

  7. typedef struct list node;

  8.  

  9. void init(node * record)

  10. {

  11.     record->next = NULL;

  12. }

  13.  

  14. void addnode(node * record, int d)

  15. {

  16.     node *fresh;

  17.     fresh = (node *) malloc(sizeof(node));

  18.     fresh->month = d;

  19.     fresh->next = record->next;

  20.     record->next = fresh;

  21. }

  22.  

  23. void print(node * record)

  24. {

  25.     node *temp;

  26.     temp = (node *) malloc(sizeof(node));

  27.     for (temp = record->next; temp; temp = temp->next)

  28.         printf(" %d", temp->month);

  29. }

  30.  

  31. void reverse(node * record)

  32. {

  33.     node *temp;

  34.     node *temp1;

  35.     node *temp2;

  36.     temp = (node *) malloc(sizeof(node));

  37.     temp1 = (node *) malloc(sizeof(node));

  38.     temp2 = (node *) malloc(sizeof(node));

  39.     temp = record;

  40.     temp1 = temp->next;

  41.     temp2 = temp1->next;

  42.     temp->next->next = NULL;

  43.     while (temp2 != NULL) {

  44.         temp = temp1;

  45.         temp1 = temp2;

  46.         temp2 = temp1->next;

  47.         temp1->next = temp;

  48.     }

  49.     record->next = temp1;

  50. }

  51.  

  52. int main(void)

  53. {

  54.     node *start;

  55.     node *start1;

  56.     start = (node *) malloc(sizeof(node));

  57.     init(start);

  58.     int i = 0;

  59.     for (i = 10; i >= 0; i--)

  60.         addnode(start, i);

  61.     print(start);

  62.     reverse(start);

  63.     printf("n");

  64.     print(start);

  65.     return 0;

  66. }

  67.  

pranjal5215

  • Jul 10th, 2009
 

This is the recursive version of the program.



Code
  1. #include<stdio.h>

  2. #include<stdlib.h>

  3. struct list {

  4.     int month;

  5.     struct list *next;

  6. };

  7. typedef struct list node;

  8. void init(node * record)

  9. {

  10.     record->next = NULL;

  11. }

  12.  

  13. void addnode(node * record, int d)

  14. {

  15.     node *fresh;

  16.     fresh = (node *) malloc(sizeof(node));

  17.     fresh->month = d;

  18.     fresh->next = record->next;

  19.     record->next = fresh;

  20. }

  21.  

  22. void print(node * record)

  23. {

  24.     node *temp;

  25.     temp = (node *) malloc(sizeof(node));

  26.     for (temp = record->next; temp; temp = temp->next)

  27.         printf(" %d", temp->month);

  28. }

  29.  

  30. node *reverse_recurse(node * cur, node * start)

  31. {                               /*reverse linked list recursively */

  32.     if (cur->next == NULL) {

  33.         start->next = cur;

  34.         return cur;

  35.     } else {

  36.         reverse_recurse(cur->next, start)->next = cur;

  37.     }

  38.     return cur;

  39. }

  40.  

  41. int main(void)

  42. {

  43.     node *start;

  44.     start = (node *) malloc(sizeof(node));

  45.     init(start);

  46.     int i = 0;

  47.     for (i = 20; i >= 0; i--)

  48.         addnode(start, i);

  49.     print(start);

  50.     reverse_recurse(start->next, start)->next = NULL;

  51.     print(start);

  52.     printf("n");

  53.     return 0;

  54. }

  55.  

  Was this answer useful?  Yes

cleonjoys

  • Oct 21st, 2010
 

This is dummy program I have written concentrating mainly on reversing the List rather than implementing efficient way in adding to list and displaying it :)

I have written Algo for the reverse also please check it for easier understanding.



Code
  1. #include <stdio.h>

  2. #include <stdlib.h>

  3.  

  4. typedef struct Node {

  5.     int info;

  6.     struct Node *next;

  7. } Node_t;

  8.  

  9. Node_t *headp = NULL;

  10.  

  11. /* Design flow

  12. .

  13. 1    rev(2) -> store NULL

  14.     2    rev(3) -> store 1

  15.         3    NULL -> store 2

  16.             ..continues after the recursive calls, so here it needs to store the previous

  17.             value

  18.    

  19. call is

  20.     reverse(start, NULL)

  21.  

  22. 1->2->3

  23. call reverse(1, NULL)

  24.         nptr = 1

  25.         prevPtr = NULL

  26.         1->next != NULL

  27.             call reverse(2, 1)

  28.             nptr = 2

  29.             prevPtr = 1

  30.             2->next != NULL

  31.                 call reverse(3, 2)

  32.                 nptr = 3

  33.                 prevPtr = 2

  34.                 3->next == NULL; so return from here

  35.    

  36.                 3->next = 2

  37.             2->next = 1

  38.         1->next = NULL

  39. */

  40.  

  41. /* Its O(n-1) in space complexity */

  42. void reverse(Node_t * nPtr, Node_t * prevPtr)

  43. {

  44.  

  45.     if (nPtr->next != NULL) {

  46.         reverse(nPtr->next, nPtr);

  47.     } else {

  48.         headp = nPtr;

  49.     }

  50.     nPtr->next = prevPtr;

  51. }

  52.  

  53. void create(int info)

  54. {

  55.  

  56.     Node_t *tPtr = NULL;

  57.     Node_t *newPtr = NULL;

  58.  

  59.     tPtr = headp;

  60.  

  61.     if ((newPtr = (Node_t *) malloc(sizeof(Node_t))) == NULL) {

  62.         printf("System OOOn");

  63.         exit(-1);

  64.     }

  65.     newPtr->info = info;

  66.     newPtr->next = NULL;

  67.  

  68.     if (headp == NULL) {

  69.         headp = newPtr;

  70.         return;

  71.     }

  72.     if (tPtr != NULL) {

  73.         while (tPtr->next != NULL)

  74.             tPtr = tPtr->next;

  75.  

  76.         tPtr->next = newPtr;

  77.     }

  78. }

  79.  

  80. void display()

  81. {

  82.     Node_t *tmpPtr = headp;

  83.  

  84.     while (tmpPtr->next != NULL) {

  85.         printf("%d ", tmpPtr->info);

  86.         tmpPtr = tmpPtr->next;

  87.     }

  88.     printf("%dn", tmpPtr->info);

  89. }

  90.  

  91. int main()

  92. {

  93.     printf("Starting creation of the List!!n");

  94.     create(1);

  95.     create(2);

  96.     create(3);

  97.     create(4);

  98.     create(5);

  99.     create(6);

  100.     create(7);

  101.  

  102.     printf("Contents of the list as follows:-n");

  103.     display();

  104.  

  105.     reverse(headp, NULL);

  106.     printf("After reverse the list has: n");

  107.     display();

  108.  

  109.     return 0;

  110.  

  111. }

  112.  

  Was this answer useful?  Yes

ss0101782

  • Dec 31st, 2010
 

Code
  1. #include"stdio.h"

  2. #include"stdlib.h"

  3. #include"conio.h"

  4. #include"string.h"

  5. #include"alloc.h"

  6. struct stud {

  7.     int roll, mtot;

  8.     char name[25];

  9.     struct stud *next;

  10. } *head, *tail;

  11. void creat();

  12. void display();

  13. void addbeg();

  14. void addend();

  15. void addany();

  16. void delet();

  17. void rev();

  18. void main()

  19. {

  20.     clrscr();

  21.     creat();

  22.     display();

  23.     printf("n ********** Add node at begining of the list **********");

  24.     addbeg();

  25.     display();

  26.     printf("n ********** Add node at end of the list **********");

  27.     addend();

  28.     display();

  29.     printf("n ********** Add node at any position of the list **********");

  30.     addany();

  31.     display();

  32.     printf("n ********** Deletion of node from the list **********");

  33.     delet();

  34.     display();

  35.     getch();

  36.     printf("n ********** Revers the list **********");

  37.     rev();

  38.     display();

  39.     getch();

  40. }

  41.  

  42. void creat()

  43. {

  44.     int i, n, k = 0, rl, mt;

  45.     char nm[25];

  46.     struct stud *p;

  47.  

  48.     printf("n Enter the number of nodes::");

  49.     scanf("%d", &n);

  50.     for (i = 0; i < n; i++) {

  51.         printf("n the node number::%d", i + 1);

  52.         printf("n Enter student roll number::");

  53.         scanf("%d", &rl);

  54.         fflush(stdin);

  55.         printf("n Enter student name::");

  56.         gets(nm);

  57.         printf("n Enter student total marks::");

  58.         scanf("%d", &mt);

  59.         fflush(stdin);

  60.         p = (struct stud *) malloc(sizeof(struct stud));

  61.         if (k == 0) {

  62.             head = p;

  63.             head->roll = rl;

  64.             strcpy(head->name, nm);

  65.             head->mtot = mt;

  66.             head->next = NULL;

  67.             k = 1;

  68.             tail = head;

  69.         } else {

  70.             head->next = p;

  71.             head = head->next;

  72.             head->roll = rl;

  73.             strcpy(head->name, nm);

  74.             head->mtot = mt;

  75.             head->next = NULL;

  76.         }

  77.     }

  78. }

  79.  

  80. void display()

  81. {

  82.     struct stud *p1;

  83.     p1 = tail;

  84.     while (p1 != NULL) {

  85.         printf("n student roll number::%4d", p1->roll);

  86.         printf("n student name ::%s", p1->name);

  87.         printf("n student total marks::%4d", p1->mtot);

  88.         printf("n--------------------------------");

  89.         p1 = p1->next;

  90.     }

  91. }

  92.  

  93. void addbeg()

  94. {

  95.     char nm[25];

  96.     struct stud *p;

  97.     int mt, rl;

  98.     printf("n Enter student roll number::");

  99.     scanf("%d", &rl);

  100.     fflush(stdin);

  101.     printf("n Enter student name::");

  102.     gets(nm);

  103.     printf("n Enter student total marks::");

  104.     scanf("%d", &mt);

  105.     fflush(stdin);

  106.     p = (struct stud *) malloc(sizeof(struct stud));

  107.     p->roll = rl;

  108.     strcpy(p->name, nm);

  109.     p->mtot = mt;

  110.     p->next = tail;

  111.     tail = p;

  112. }

  113.  

  114. void addend()

  115. {

  116.     char nm[25];

  117.     struct stud *p;

  118.     int mt, rl;

  119.     printf("n Enter student roll number::");

  120.     scanf("%d", &rl);

  121.     fflush(stdin);

  122.     printf("n Enter student name::");

  123.     gets(nm);

  124.     printf("n Enter student total marks::");

  125.     scanf("%d", &mt);

  126.     fflush(stdin);

  127.     p = (struct stud *) malloc(sizeof(struct stud));

  128.     p->roll = rl;

  129.     strcpy(p->name, nm);

  130.     p->mtot = mt;

  131.     p->next = NULL;

  132.     head->next = p;

  133.     head = p;

  134. }

  135.  

  136. void addany()

  137. {

  138.     char nm[25];

  139.     struct stud *p, *p1;

  140.     int mt, rl, n, k = 0, c = 0;

  141.     printf("n Enter the position where you want to add the node::");

  142.     scanf("%d", &n);

  143.     fflush(stdin);

  144.     if (n <= 0) {

  145.         printf("n wrong entry::");

  146.         getch();

  147.         exit(1);

  148.     }

  149.     p = (struct stud *) malloc(sizeof(struct stud));

  150.     printf("n Enter student roll number::");

  151.     scanf("%d", &rl);

  152.     fflush(stdin);

  153.     printf("n Enter student name::");

  154.     gets(nm);

  155.     printf("n Enter student total marks::");

  156.     scanf("%d", &mt);

  157.     fflush(stdin);

  158.     p->roll = rl;

  159.     strcpy(p->name, nm);

  160.     p->mtot = mt;

  161.     p1 = tail;

  162.     n = n - 1;

  163.     while (p1 != NULL) {

  164.         c++;

  165.         if (c == n) {

  166.             p->next = p1->next;

  167.             p1->next = p;

  168.             k = 1;

  169.             break;

  170.         }

  171.         p1 = p1->next;

  172.     }

  173.     if (k == 0)

  174.         printf("n sorry position not found::");

  175. }

  176. void delet()

  177. {

  178.     char nm[25];

  179.     struct stud *p, *p1;

  180.     int mt, rl, k = 0;

  181.     printf("n Enter student's roll number which is to be deleted::");

  182.     scanf("%d", &rl);

  183.     fflush(stdin);

  184.     p1 = tail;

  185.     // p=head1;

  186.     while (p1 != NULL) {

  187.         k++;

  188.         if (p1->roll == rl) {

  189.             if (k == 1)

  190.                 tail = p1->next;

  191.             else

  192.                 p->next = p1->next;

  193.             free(p1);

  194.             break;

  195.         }

  196.         p = p1;

  197.         p1 = p1->next;

  198.     }

  199.     if (k == 0)

  200.         printf("n node position not found::");

  201. }

  202. void rev()

  203. {

  204.     char nm[25];

  205.     struct stud *p, *p1, *temp = NULL;

  206.     int mt, rl;

  207.     p1 = tail;

  208.     while (p1 != NULL) {

  209.         p = (struct stud *) malloc(sizeof(struct stud));

  210.         p->roll = p1->roll;

  211.         strcpy(p->name, p1->name);

  212.         p->mtot = p1->mtot;

  213.         p->next = temp;

  214.         temp = p;

  215.         p1 = p1->next;

  216.         free(tail);

  217.         tail = p1;

  218.     }

  219.     tail = temp;

  220. }

  221.  

  Was this answer useful?  Yes

ankit srivastava

  • Oct 17th, 2011
 

public void ReverseLinkedList (LinkedList linkedList)
{
// ------------------------------------------------------------
// Create a new linked list and add all items of given
// linked list to the copy linked list in reverse order
// ------------------------------------------------------------

LinkedList copyList = new LinkedList();

// ------------------------------------------------------------
// Start from the latest node
// ------------------------------------------------------------

LinkedListNode start = linkedList.Tail;

// ------------------------------------------------------------
// Traverse until the first node is found
// ------------------------------------------------------------

while (start != null)
{
// ------------------------------------------------------------
// Add item to the new link list
// ------------------------------------------------------------

copyList.Add (start.Item);

start = start.Previous;
}

linkedList = copyList;

// ------------------------------------------------------------
// That's it!
// ------------------------------------------------------------
}

  Was this answer useful?  Yes

samCPP

  • Dec 4th, 2011
 

Reversing a Linked list using temporary pointer


Code
  1. #include<iostream.h>

  2. #include<conio.h>

  3. using namespace std;

  4. template < class T > struct node {

  5.     int element;

  6.      node < T > *next;

  7.      node() {

  8.     } node(const T element) {

  9.         this->element = element;

  10.         this->next = NULL;

  11.     }

  12.     node(const T element, node < T > *next) {

  13.         this->element = element;

  14.         this->next = next;

  15.     }

  16. };

  17.  

  18. template < class T > class linkedlist {

  19.   private:

  20.     node < T > *top;

  21.   public:

  22.     linkedlist() {

  23.         top = NULL;

  24.     }

  25.     ~linkedlist() {

  26.         node < T > *newnode = top->next;

  27.         delete[]top;

  28.         top = newnode;

  29.     }

  30.     void push(const T ele) {

  31.         top = new node < T > (ele, top);

  32.     }

  33.     void display() {

  34.         node < T > *p;

  35.         p = top;

  36.         while (p != NULL) {

  37.             cout << p->element << "   ";

  38.             p = p->next;

  39.         }

  40.     }

  41.     void reverse() {

  42.         node < T > *p, *d;

  43.         p = top;

  44.         d = NULL;

  45.         while (p != NULL) {

  46.             d = new node < T > (p->element, d); //Temporary pointer for reversal

  47.             p = p->next;

  48.         }

  49.         top = d;

  50.         while (d != NULL) {

  51.             cout << d->element << "    ";

  52.             d = d->next;

  53.         }

  54.         cout << endl;

  55.         free(d);

  56.     }

  57. };

  58.  

  59. int main()

  60. {

  61.     linkedlist < int >a;

  62.     int ele, ch;

  63.     while (1) {

  64.         cout << "Enter choice";

  65.         cin >> ch;

  66.         switch (ch) {

  67.  

  68.         case 1:

  69.  

  70.             cout << "enter element ";

  71.             cin >> ele;

  72.             a.push(ele);

  73.             break;

  74.  

  75.         case 2:

  76.  

  77.             cout << " List is " << endl;

  78.             a.display();

  79.             break;

  80.  

  81.         case 3:

  82.  

  83.             cout << " Reverse List is " << endl;

  84.             a.reverse();

  85.             break;

  86.  

  87.         case 4:

  88.  

  89.             return 0;

  90.         }

  91.     }

  92.     getch();

  93.     return 0;

  94. }

  95.  

  Was this answer useful?  Yes

Give your answer:

If you think the above answer is not correct, Please select a reason and add your answer below.

 

Related Answered Questions

 

Related Open Questions