Scribd
Upload
171 views

Sorting and Reversing A Linked List

To sort a linked list, the program traverses the list and moves the node with the minimum data value to a new list. This process repeats until the original list is empty. To reverse a linked list, the program uses three pointers - previous, current and next. It updates the current node's link to point to the previous node, moves the pointers ahead and repeats this until the end of the list. The program includes functions to insert nodes, print the list, sort the list by moving minimum nodes, and reverse the list by changing link pointers.

Uploaded by

hasibujtaba
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
171 views

Sorting and Reversing A Linked List

To sort a linked list, the program traverses the list and moves the node with the minimum data value to a new list. This process repeats until the original list is empty. To reverse a linked list, the program uses three pointers - previous, current and next. It updates the current node's link to point to the previous node, moves the pointers ahead and repeats this until the end of the list. The program includes functions to insert nodes, print the list, sort the list by moving minimum nodes, and reverse the list by changing link pointers.

Uploaded by

hasibujtaba
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

SORTING AND REVERSING A LINKED LIST

Introduction
To sort a linked list, first we traverse the list searching for the node with a minimum data value. Then we remove that node and append it to another list which is initially empty. We repeat this process with the remaining list until the list becomes empty, and at the end, we return a pointer to the beginning of the list to which all the nodes are moved, as shown in Figure 20.1.

Figure 20.1: Sorting of a linked list. To reverse a list, we maintain a pointer each to the previous and the next node, then we make the link field of the current node point to the previous, make the previous equal to the current, and the current equal to the next, as shown in Figure 20.2.

Figure 20.2: A linked list showing the previous, current, and next nodes at some point during reversal process. Therefore, the code needed to reverse the list is
Prev = NULL; While (curr != NULL) { Next = curr->link; Curr -> link = prev; Prev = curr; Curr = next; }

Program
# include <stdio.h> # include <stdlib.h> struct node { int data; struct node *link; }; struct node *insert(struct node *p, int n) { struct node *temp; if(p==NULL) { p=(struct node *)malloc(sizeof(struct node)); if(p==NULL) {

printf("Error\n"); exit(0); } p-> data = n; p-> link = NULL; } else { temp = p; while (temp-> link!= NULL) temp = temp-> link; temp-> link = (struct node *)malloc(sizeof(struct node)); if(temp -> link == NULL) { printf("Error\n"); exit(0); } temp = temp-> link; temp-> data = n; temp-> link = null; } return(p); } void printlist ( struct node *p ) { printf("The data values in the list are\n"); while (p!= NULL) { printf("%d\t",p-> data); p = p-> link; } } /* a function to sort reverse list */ struct node *reverse(struct node *p) { struct node *prev, *curr; prev = NULL; curr = p; while (curr != NULL) { p = p-> link; curr-> link = prev; prev = curr; curr = p; } return(prev); } /* a function to sort a list */ struct node *sortlist(struct node *p) { struct node *temp1,*temp2,*min,*prev,*q; q = NULL; while(p != NULL) { prev = NULL; min = temp1 = p; temp2 = p -> link; while ( temp2 != NULL ) { if(min -> data > temp2 -> data) { min = temp2; prev = temp1; }

temp1 = temp2; temp2 = temp2-> link; } if(prev == NULL) p = min -> link; else prev -> link = min -> link; min -> link = NULL; if( q == NULL) q = min; /* moves the node with lowest data value in the list pointed to by p to the list pointed to by q as a first node*/ else { temp1 = q; /* traverses the list pointed to by q to get pointer to its last node */ while( temp1 -> link != NULL) temp1 = temp1 -> link; temp1 -> link = min; /* moves the node with lowest data value in the list pointed to by p to the list pointed to by q at the end of list pointed by q*/ } } return (q); } void main() { int n; int x; struct node *start = NULL ; printf("Enter the nodes to be created \n"); scanf("%d",&n); while ( n- > 0 ) { printf( "Enter the data values to be placed in a node\n"); scanf("%d",&x); start = insert ( start,x); } printf("The created list is\n"); printlist ( start ); start = sortlist(start); printf("The sorted list is\n"); printlist ( start ); start = reverse(start); printf("The reversed list is\n"); printlist ( start ); }

Explanation The working of the sorting function on an example list is shown in Figure 20.3.

Figure 20.3: Sorting of a linked list. The working of a reverse function is shown in Figure 20.4.

Figure 20.4: Reversal of a list.

You might also like