5. Linked Lists

We will create the function deleteTheNumber that has two parameters: runner of type ListNode* and x of type int. The parameter runner points to the first element of the list, and the parameter x is the number that is to be deleted. The function will delete the first occurrence of x in the list, unless the value x is also in the head. If the value x is also in the head, then the function will delete the second occurrence. Therefore the function will not immediately solve the required problem. In order to solve the problem, we will actually apply the function to a modified list: we will add an artificial head to the original list, and then apply the function to this new extended list. This will guarantee that it works even in the case when the first element contains x.

The entire program is given below and explanations are written in comments.

// example_linkedList.cpp
 // compile with
 // c++ example_linkedList.cpp -o example_lList -std=c++11
 // execute with
 // ./example_lList
 
#include <iostream>
struct ListNode{
    long content;
    ListNode* aNext;
};
void freeTheMemory(ListNode *runner){
    if( runner!=nullptr){
        freeTheMemory((*runner).aNext);
        delete runner;
    }
}
void deleteTheNumber(ListNode* runner, int x){
    if(runner->aNext!=nullptr){
        if((runner->aNext)->content==x){
            ListNode *temp=runner->aNext;
            runner->aNext=(runner->aNext)->aNext;
            delete temp;
        }
        else{
            deleteTheNumber(runner->aNext,x);
        }
    }
}
int main(){
    int userInput;
    ListNode* head;
    std::cout << "Insert the first element of the list: ";
    std::cin>>userInput;
    head=new ListNode;
    (*head).content=userInput;
    (*head).aNext=nullptr;
    ListNode *runner;
    runner=head;
    while(userInput!=-9){
        std::cout << "Insert an element of the list (-9 for the end): ";
        std::cin>>userInput;
        if(userInput!=-9){
            // *runner is the last node in the list (tail)
            // (*runner).aNext is currently nullptr
            // We now allocate new memory for ListNode and make
            // (*runner).aNext to contain the address
            // of this new ListNode
            (*runner).aNext=new ListNode;
            // runner is no more pointing to the tail
            // The next line updates the runner to point
            // to the newly created tail
            runner=(*runner).aNext;
            // We now set the content of the tail
            (*runner).content=userInput;
            // and make sure that the tail‘s pointer
            // to the the next is set to nullptr
            (*runner).aNext=nullptr;
        }
    }
    std::cout << "Which number to delete? ";
    std::cin>>userInput;
    runner=new ListNode;
    runner->aNext=head;
    deleteTheNumber(runner,userInput);
    head=runner->aNext;
    ListNode *saver=runner;
    std::cout << "List printout: " << std::endl;
    runner=head;
    while(runner!=nullptr){
        std::cout << (*runner).content << " ";
        runner=(*runner).aNext;
    }
    std::cout << std::endl;
    // FREEING THE MEMORY
    freeTheMemory(saver);
    return 0;}

The comments in the code below contain the main idea and the explanations for the steps taken in solving the problem.

// linkedListDeleteLast.cpp
// compile with
// c++ linkedListDeleteLast.cpp -o lLDL -std=c++11
// execute with
 // ./lLDL

 #include <iostream>
 class ListNode{
 public:
    long content;
    ListNode *aNext;
 };
 void freeTheMemory(ListNode *runner){
    if( runner!=nullptr){
        freeTheMemory((*runner).aNext);
        delete runner;
    }
}
 // The following function takes three parameters: 
 // 1) head is the pointer to the beginning of the list;
 // 2) pIndicator is the pointer to the location in RAM that contains
 //    the integer that is 0 or 1. When the function is first called, 
 //    this location in RAM should contain the value 0. 
 //    At the end, the value 1 indicates that  x  is successfully removed 
 //    from the list and the value 0 indicates that x was not found
 //    in the list. The function will return the pointer to the head 
//     of the new list.
 ListNode* deleteLastNumber(ListNode *head, int * pIndicator, int x){
    if(head!=nullptr){
        // Since we must delete the last occurrence of x, we will first try 
        // to delete it from the tail  
        if((*head).aNext!=nullptr){
            // We will call the function recursively on (*head).aNext. 
            // The function will remove x from the tail.
            // The function will return the pointer to the new head of the 
            // tail. The new head is the same as the old first element 
            // (i.e. head) of the tail, unless the first node of the tail 
            // contains the only x in  the  tail. If latter was the case, 
            // then the function deleted the head of the tail and 
            // returned the pointer to the next element. 
            // The assignment operator will re-wire the list so that the 
            // (*head).aNext now points to correct node.
            (*head).aNext=deleteLastNumber((*head).aNext,pIndicator,x);
        }
        // If the value *pIndicator is 1, then the value x is found in the  
        // tail and successfully removed from the tail. In this case we 
        // don‘t care whether the head contains x.
        if(((*head).content==x)&&(*pIndicator==0)){
            // If the program has entered this block of code, 
            // then it means that the head contains x,
            // and there is no other x in the tail of the list.
            // If this is the case, we will remove the head of the list.
            // We will need to re-wire the list so that 
            ListNode *newHead;
            newHead=(*head).aNext;
            (*head).aNext=nullptr;
            delete head;
            head=newHead;
            // It remains to set the indicator to 1, since the node with x 
            // is removed.
            *pIndicator=1;
        }
    }
    return head;
 }
 int main(){
    int userInput;
    ListNode *head;
    std::cout<<"Insert the first element of the list: ";
    std::cin>>userInput;
    head=new ListNode;
    (*head).content=userInput;
    (*head).aNext=nullptr;
    ListNode *runner;
    runner=head;
    while(userInput!=-9){
        std::cout<<"Insert an element of the list (-9 for the end): ";
        std::cin>>userInput;
        if(userInput!=-9){
            // *runner is the last node in the list (tail)
            // (*runner).aNext is currently nullptr
            // We now allocate new memory for ListNode and make
            // (*runner).aNext to contain the address
            // of this new ListNode
            (*runner).aNext=new ListNode;
            // runner is no more pointing to the tail
            // The next line updates the runner to point
            // to the newly created tail
            runner=(*runner).aNext;
            // We now set the content of the tail
            (*runner).content=userInput;
            // and make sure that the tail‘s pointer
            // to the the next is set to nullptr
            (*runner).aNext=nullptr;
        }
    }
    std::cout<<"Which number to delete? ";
    std::cin>>userInput;
    int indicator=0;
    head=deleteLastNumber(head,&indicator,userInput);
    std::cout<<"List printout: "<<std::endl;
    runner=head;
    while(runner!=nullptr){
        std::cout<<(*runner).content<<" ";
        runner=(*runner).aNext;
    }
    std::cout<<std::endl;
    // FREEING THE MEMORY
    freeTheMemory(head);
    return 0;
 }

We will solve this problem recursively. The recursive call will be made with the argument aH->aNext.

We will now develop the main idea for the recursion. The parameter of the function is the head of the list aH. We will call this list blue list. Let us give the name green list to the list obtained from the original blue list by removing the head node.

We make a recursive call with the argument aH->aNext. The recursive call will reverse the green list and return the result eR that points to the head of the new list.

It remains to re-wire the very last node of the green list in such a way that its component aNext becomes aH. The last node of the green list is (aH->aNext)->aNext. Therefore, the command to make the required re-wiring is

(aH->aNext)->aNext=aH; 

The pointer aH->aNext will be changed into nullptr. The head of the resulting reversed list is eR.

#include<iostream>
class ListNode{
public:
  long cont;
  ListNode* aNext;
}; 
ListNode* reverseList(ListNode* aH){
    if(aH==nullptr){return aH;}
    if((*aH).aNext==nullptr){return aH;}
    ListNode* eR;// employee's result
    eR=reverseList((*aH).aNext);
    (aH->aNext)->aNext=aH;
    (*aH).aNext=nullptr;
    return eR;
}
ListNode* listFromInput(long c){
  if(c<0){
    return nullptr;
  }
  long x;
  std::cin>>x;
  ListNode* aHead=new ListNode;
  aHead->cont=c;
  aHead->aNext=listFromInput(x);
  return aHead;
}
ListNode* listFromInput(){
  long c;
  std::cin>>c;
  return listFromInput(c);
}
std::string listToString(ListNode* aH){
  if(aH==nullptr){return "";}
  return std::to_string(aH->cont)+" "+listToString(aH->aNext);
}
void freeTheMemory(ListNode* aH){
  if(aH!=nullptr){
    freeTheMemory(aH->aNext);
    delete aH;
  }
}
int main(){
  ListNode* aHead=listFromInput();
  std::cout<<listToString(aHead)<<"\n";
  aHead=reverseList(aHead);
  std::cout<<listToString(aHead)<<"\n";
  freeTheMemory(aHead);
  return 0;
}