FOR FREE MATERIALS

A linked list can be created using a ‘structure’ in programming. 

Each node of the linked list should contain the two parts-

# The Data Part

# The Address Part

The program is written to reverse the list physically. For performing this first the original linked list is copied to another linked list. Let the list be:

Three-pointers are taken to reverse the list physically. The pointer ‘mid’ point to the node whose address part (link) is to be changed, the pointer ‘left’ will point the node which the ‘mid’ will be pointing to reverse the list, and the pointer ‘right’ will point to the node which is previously pointed by ‘mid’.

In the beginning, both the ‘left’ and ‘right’ pointer will be null. And the ‘mid’ will point to the first node of the list.

A loop will be executed till the last node i.e. till the ‘mid’ becomes null. 

The pointer ‘right’ will point to the next node of ‘mid’, the ‘mid’ will point to the node pointed by ‘pointer’. Then the ‘left’ pointer will point to ‘mid’ and ‘mid’ will point to ‘right’.

So, for the first time, the value of ‘left’ is null, therefore, the address part of the ‘mid’ will be initialized with null.

After this, the linked list will be:

Again the same process will be continued i.e. the address part of the pointer ‘mid’ will be pointing to the node pointed by ‘left’ which makes the list reverse.

The list after this will be:

The same process will be continued and after each step, the links of the linked list will be changed as:

After completing the linking process the ‘head’ will be pointed to the last node of the list.

INPUT:  The number of elements to create the list and the elements which are to be inserted.
OUTPUT:  a) The list after creating it.
	        b) The list after reversing it.
PROCESS:
Step 1: Define a structure named ‘node’ which has two parts−
•	The data part of integer type.
•	The ‘next’ (points to it’s next node i.e. the address of the next node) part which is a structure(node) type pointer.

Step 2: Create a function “void createlist()”
 Step 2.1: Take the number of  elements from user in an ‘integer’ type variable ‘n’
 Step 2.2: For i=0 to (n-1) repeat  Step 2.3 to Step 2.7
 Step 2.3: Take the element which is to be inserted in an integer type variable  ‘x’.
 Step 2.4: Create a new node in ‘p’(a ‘node’ type pointer) by using ‘malloc’ function.                    
Set data[p] <- x
	          Set next[p] <- Null
 Step 2.5: If (head1 = Null) then
                     		Set head1 <- p
	           [End of ‘If’ ]
 Step 2.6: Else   
            		Set next[ptr] <- p
	            [End of ‘Else’] 

 Step 2.7: Set ptr <- p

                [End of  Step 2.2 ‘For’ loop]
[End of  the function “void createlist( )”]   

Step 3: Create a function “void displaylist()”
 Step 3.1: Set p <-head1
 Step 3.2: While(p≠Null) then repeat  Step 3.3 and Step 3.4
 Step 3.3: Print  data[p]
 Step 3.4: Set p<-next[p]	
[End of  Step 3.2 ‘While’ loop]
[End of  the function “void displaylist( )”]

Step 4: Create a function “void revlist()”
 Step 4.1: Set left<-NULL
 Step 4.2: Set mid<-head1
 Step 4.3: Set right<-NULL
 Step 4.4: while mid ≠ NULL repeat step 4.5 to step 4.8
 Step 4.5: Set right <-next [mid]  
 Step 4.6: Set next [mid] <- left 
 Step 4.7: Set left<- mid
 Step 4.8: Set mid <- right 
   [End of step 4.4 ‘while’ loop]
 Step 4.9: Set head1 <- left
[End of function ‘revlist()’] 

Step 5: [Function ‘main()’]
 Call the function ‘createlist()’
 Call the function ‘displaylist()’
 Call the function ‘revlist()’

Step 6: Stop.