4-Ans- This question has many answers. Both recursive and non-recursive solutions are possible.
Also we can modify the original input to reverse the Linked List or we can generate a new Linked List which will be the reversed version of the original input.
Thus we can have 4 types of solutions :
A) Recursive solution.
A.1) DO Modify the original input, DO NOT create new Linked List.
A.2) DO NOT Modify the original input, DO create new Linked List.
B) Non-Recursive solution.
B.1) DO Modify the original input, DO NOT create new Linked List.
B.2) DO NOT Modify the original input, DO create new Linked List.
Here we shall discuss all the 4 types of solutions.
Solution for A.1 - DO Modify the original input, DO NOT create new Linked List in Recursive way.
Here are the steps to be followed : (click here to view a pictorial representation for this algorithm.)
-1) Take the starting node of the Linked List as input, let the node be S .
-2) Call procedure REV_REC_MOD by passing the node S in it.
( REV_REC_MOD will return you the starting node of the reversed Linked List)
-3) Define REV_REC_MOD : gets a single node NODE as argument , and returns a node.
-4) If ( NODE== NULL ) , Or, ( NODE-->Next == NULL ) , then return NODE .
-5) Create a new node pointer TEMP and set TEMP = NODE --> NEXT .
-6) set NODE --> NEXT = NULL.
-7) Create a new node pointer RESULT and set RESULT = REV_REC_MOD (TEMP ).
-8) Create a new node pointer TRACK and set TRACK = RESULT .
-9) Loop Start: While ( TRACK --> NEXT != NULL )
-10) set TRACK = TRACK --> NEXT .
-11) Loop End.
-12) set TRACK --> NEXT = NODE.
-13) Return RESULT .
-14)End REV_REC_MOD .
Solution for A.2 - DO NOT Modify the original input, DO create new Linked List in Recursive way.
The steps are almost same as the previous algorithm, the only difference is that,
here we instead of using the original node, create a new new node every time.
Here are the steps : (click here to view a pictorial representation for this algorithm.)
-1) Take the starting node of the Linked List as input, let the node be S .
-2) Call procedure REV_REC_NEW by passing the node S in it.
( REV_REC_NEW will return you the starting node of the reversed Linked List)
-3) Define REV_REC_NEW : gets a single node NODE as argument , and returns a node.
-4) If ( NODE== NULL ) , then return NODE .
-5) Or If, ( NODE-->Next == NULL ) , then,
-6) create a new node pointer RET .
-7) set RET --> VALUE = NODE --> VALUE, and RET --> NEXT = NULL .
-8) Return RET .
-9) End If.
-10) Create a new node pointer TEMP and set TEMP = NODE --> NEXT .
-11) Create a new node pointer COPY and set COPY --> VALUE = NODE --> VALUE.
-12) set COPY --> NEXT = NULL.
-13) Create a new node pointer RESULT and set RESULT = REV_REC_NEW (TEMP ).
-14) Create a new node pointer TRACK and set TRACK = RESULT .
-15) Loop Start: While ( TRACK --> NEXT != NULL )
-16) set TRACK = TRACK --> NEXT .
-17) Loop End.
-18) set TRACK --> NEXT = COPY.
-19) Return RESULT .
-20) End REV_REC_NEW .
Solution for B.1 - DO Modify the original input, DO NOT create new Linked List in Non-Recursive way.
Here are the steps : (click here to view a pictorial representation for this algorithm.)
-1) Take the starting node of the Linked List as input, let the node be S .
-2) If ( S == NULL ) , Or, ( S -->Next == NULL ) , then return S .
-3) Otherwise, create a new node pointer TRACK and set TRACK = S .
-4) Create a new node pointer PREV and set PREV = NULL .
-5) Create a new node pointer TEMP and set TEMP = NULL .
-6) Loop Start: While ( TRACK != NULL )
-7) set TEMP = TRACK --> NEXT .
-8) set TRACK --> Next = PREV .
-9) set PREV = TRACK .
-10) set TRACK = TEMP .
-11)Loop End.
-12)Return PREV .
Solution for B.2 - DO NOT Modify the original input, DO create new Linked List in Non-Recursive way.
Here are the : (click here to view a pictorial representation for this algorithm.)
-1) Take the starting node of the Linked List as input, let the node be S .
-2) If ( S == NULL ) , Or, ( S -->Next == NULL ) , then return S .
-3) Otherwise, create a new node pointer R and set R = NULL .
-4) Loop Start: While ( S != NULL )
-5) Create a new node pointer TEMP and set TEMP --> Value = S -->Value .
-6) set TEMP --> Next = R .
-7) set R = TEMP .
-8) set S = S --> Next .
-9) Loop End.
-10)Return R .