We will create the function with the declaration
ListElement* reverseAndReturnLast(ListElement* aF, ListElement* aL)
that takes two pointers
aF
and
aL
to the first and last element of a subset of a linked list. The function reverses the pointers in this subset and returns the pointer
aL
. The function is implemented recursively. The obtained function is used in
reverseTheList
whose arguments are the pointer to the head of the list and two numbers
st
and
en
. The function
reverseTheList
identifies the nodes that contain the numbers
st
and
en
and calls the function
reverseAndReturnLast
to reverse the pointers in the subset of the list.
#include<iostream>
struct ListElement{
public:
long content;
ListElement* aNext;
};
void printList(ListElement* aH){
if(aH!=nullptr){
std::cout<< (*aH).content<<"\t";
printList((*aH).aNext);
}
}
void delList(ListElement* aH){
if(aH!=nullptr){
delList((*aH).aNext);
delete aH;
}
}
ListElement* reverseAndReturnLast(ListElement* aF, ListElement* aL){
if(aF->aNext == aL){
ListElement* aTail = aL->aNext;
aL->aNext=aF;
aF->aNext=aTail;
return aL;
}
reverseAndReturnLast(aF->aNext,aL);
ListElement* aTail= (aF->aNext)->aNext;
(aF->aNext)->aNext=aF;
aF->aNext=aTail;
return aL;
}
ListElement* pointerToNodeBefore(ListElement* aH, long x){
if(aH==nullptr){
return nullptr;
}
if(aH->aNext==nullptr){
return nullptr;
}
if((aH->aNext)->content==x){
return aH;
}
return pointerToNodeBefore(aH->aNext,x);
}
ListElement* reverseTheList(ListElement* aH, long st, long en){
ListElement* aNH=new ListElement;
aNH->aNext=aH;
long absSt=st, absEn=en;
if(absSt<0.0){absSt *= -1;}
if(absEn<0.0){absEn *= -1;}
aNH->content = absSt+absEn+1;
// Now we are sure that the new list with head aNH
// does not start with st and does not start with en.
//Step 1: Find the pointer to the node before the one that
// contains st;
ListElement* aBF=pointerToNodeBefore(aNH,st);
if(aBF==nullptr){
delete aNH;
return aH;
}
ListElement* aBL=pointerToNodeBefore(aBF->aNext,en);
if(aBL==nullptr){
delete aNH;
return aH;
}
aBF->aNext = reverseAndReturnLast(aBF->aNext,aBL->aNext);
aH=aNH->aNext;
delete aNH;
return aH;
}
int main(){
ListElement* aH=nullptr, *aRunner;
long uI;
std::cin>>uI;
if(uI>0){
aH=new ListElement;
aH->aNext=nullptr;
aH->content=uI;
std::cin>>uI;
aRunner=aH;
while(uI>0){
aRunner->aNext=new ListElement;
aRunner=aRunner->aNext;
aRunner->content=uI;
aRunner->aNext=nullptr;
std::cin>>uI;
}
long st,en;
std::cin>>st>>en;
printList(aH);
std::cout << "\n";
aH=reverseTheList(aH,st,en);
printList(aH);
std::cout << "\n";
}
return 0;
}