5-Ans- This question can be solved in four simple steps:
--1) Find the middle node of the Linked List.
(Note : if the list has odd number of nodes, then there will be a single middle,
else there will be two middle nodes.)
--2) Reverse the second half of the Linked List.
(see Linked List Question-4 to get a suitable Linked List Reversal algorithm.)
--3) Compare the first half and second half nodes. These comparisons will fetch you the result.
But do not return the result immediately.
--4) Reverse the second half again to get back the original list, and finally, return result.
Here are the steps explained:
-1) Take the starting node of the Linked List as input, let the node be HEAD.
-2) If ( HEAD == NULL ) , Or, ( HEAD -->Next == NULL ) , then return HEAD .
-3) Create new node pointers S1 and S2 , and set S1 = HEAD, and S2 = HEAD .
-4) Start LOOP: While ( S2 != NULL And S2 --> NEXT != NULL )
-5) S1 = S1 --> NEXT.
-6) S2 = S2 --> NEXT --> NEXT.
-7) End LOOP.
-8) Create a new node TEMP.
-9) If ( S2 == NULL ), then set TEMP = S1, Otherwise set TEMP = S1 --> NEXT.
-10) Create a new node REVERSE_HEAD, and set REVERSE_HEAD = RVERSE_LINKED_LIST ( TEMP ).
(the procedure RVERSE_LINKED_LIST is used to reverse a Linked List, it is described below. )
-11) Create a new node REVERSE_HEAD_COPY, and set REVERSE_HEAD_COPY = RVERSE_HEAD.
-12) Create a variable RESULT, and initially set RESULT = TRUE.
-13) Start LOOP : While ( TRUE )
-14) If ( REVERSE_HEAD --> VALUE != HEAD --> VALUE )
-15) set RESULT = FALSE, and break out of the LOOP.
-16) End If.
-17) If ( REVERSE_HEAD == TEMP )
-18) break out of the LOOP.
-19) End If.
-20) REVERSE_HEAD = REVERSE_HEAD --> NEXT.
-21) HEAD = HEAD --> NEXT .
-22) End LOOP.
-23) call RVERSE_LINKED_LIST ( REVERSE_HEAD_COPY ).
-24) return RESULT.
Click here to view a pictorial description of the above mentioned algorithm.
The algorithm for procedure RVERSE_LINKED_LIST
[this is just same as solution B.1 for Linked List Question-4]:
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 .