FOR FREE YEAR SOLVED

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. 

For performing this first the original linked list is copied to another  linked list. 

Let the list be:

In that case, we physically reverse the linked list:

For reversing the list two pointers are used. One is to point at the last node and one node before that.

For the first time, the two pointers pointing to the aforesaid nodes are:

A new node will be created pointed by the pointer ‘p’ which will store the data of the node pointed by ‘ptr’.

Now, this node  will  be inserted into a new list.

The address part of the node pointed by ‘ptr1’ will be made NULL which will de-touch the last node from the list.

So, the new list after deleting the last node the original list is:

Again, the same process  will be repeated. The position of the pointers will be:

Now the new node will be created with the data 3:

This node will be appended to the new list. After appending the new list will be:

Again the address part of the node pointed by ‘ptr1’ will be replaced with Null.

The original list will be:

This process will be continued till the last node of the list. And we will get the reversed list as:

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 ptr<-head1
 Step 4.2: Set head3<-NULL
 Step 4.3: while ptr≠NULL repeat Step 4.4 to Step 4.7
 Step 4.4: Create a new node in ‘p’(a ‘node’ type pointer) by using ‘malloc’ function.                    
   Set data[p] <- data[ptr]
   Set next[p] <- Null
 Step 4.5: if head3=NULL then
   Set head3<-p
	else
   Set next[ptr3]<-p
   [End of Step 4.5 ‘if’]
 Step 4.6: Set ptr3<-p
 Step 4.7: Set ptr<-next[ptr]
   [End of 4.3 ‘while’ loop]
 Step 4.8: while head3≠NULL repeat Step 4.9 to 4.14
 Step 4.9: Set ptr<-head3
 Step 4.10: while next[ptr]≠NULL repeat Step 4.11 to 4.12
 Step 4.11: Set ptr1<-ptr
 Step 4.12: Set ptr=next[ptr]
   [End of Step 4.10 ‘while’ loop]
 Step 4.11: Create a new node in ‘p’(a ‘node’ type pointer) by using ‘malloc’ function.                    
   Set data[p] <- data[ptr]
   Set next[p] <- Null
 Step 4.12: if head3=ptr then
   Set head3<-NULL
	 else
   Set next[ptr1]<-NULL
	 [End of Step 4.12 ‘if’]
 Step 4.13: if head2=NULL then
   Set head2<-p
	else
   next[ptr2]<-p
   [End of Step 4.13 ‘if’]
 Step 4.14: Set ptr2<-p
   [End of step 4.8 ‘while’ loop]
 Step 4.15: Set p<-head2
 Step 4.16: Print "The reverse list is:"
 Step 4.17: while p≠NULL repeat Step 4.18 and 4.19
 Step 4.18: Print data[p]
 Step 4.19: Set p<-next[p]
  [End of Step 4.17 ‘while’ loop]
  [End of function ‘revlist()’]

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