Answer to Question #268382 in C++ for noor

Question

Linked List in c++.

1:Write a function to delete a node from end. 2. Write a function to delete a node at given position. 3. Write a function to get the middle the linked list (only use single pointer i.e. head) 4. write a function to move last to nodes of a linked list to the front. Example: 1->2->3->4->5, then the function should change the list to 5->4->1->2->3. 5. Write a function to remove nodes with similar data in a given linked list.

Answer 1

function to delete a node from end

void pop_back() {
  if(head != NULL) {
    
    //1. if head in not null and next of head
    //   is null, release the head
    if(head->next == NULL) {
      head = NULL;
    } else {
      
      //2. Else, traverse to the second last 
      //   element of the list
      Node* temp = head;
      while(temp->next->next != NULL)
        temp = temp->next;
      
      //3. Change the next of the second 
      //   last node to null and delete the
      //   last node
      Node* lastNode = temp->next;
      temp->next = NULL;
      free(lastNode); 
    }
  }

}

Write a function to delete a node at given position

void deleteNode(struct LLNode **head_ref, int pos)
{
    //
   if (*head_ref == NULL)
   {
      return;
   }
   //temp to store head
   struct LLNode* temp = *head_ref;
   //Delete head node
    if (pos == 0)
    {
        *head_ref = temp->next; 
        free(temp);               
        return;
    }
    //store previous of to be deleted node
    for (int i=0; temp!=NULL && i<pos-1; i++)
    {
        temp = temp->next;
    }
    if (temp == NULL || temp->next == NULL)
    {
        return;
    }
    //delete node at pos (next of pos-1)
    struct LLNode *next = temp->next->next;
    free(temp->next);  
    temp->next = next; 
}

function to get the middle the linked list 

int middleOfList(struct LL**head)
{
  
  struct LL*slow=*head,*fast=*head;
  while(fast&&fast->next) //if fast not NULL and fast's next is not NULL because it takes two steps
    {
      slow=slow->next; //move this with speed x
      fast=fast->next->next; //move this with speed 2x
    }
  return  slow->data; //middle of list
  //O(number of nodes)
}
void display(struct LL**head)
{
  struct LL*temp=*head;
  while(temp!=NULL)
    {
      if(temp->next!=NULL)
      cout<<temp->data<<" ->";
      else
      cout<<temp->data;
      
      temp=temp->next; //move to next node
    }
    //O(number of nodes)
  cout<<endl;
}

Function to move the last node to the front of a given linked list

void rearrange(struct Node** head)
{
    // proceed only when the list is valid
    if (!*head || !(*head)->next) {
        return;
    }
 
    struct Node* ptr = *head;
 
    // move to the second last node
    while (ptr->next->next) {
        ptr = ptr->next;
    }
 
    // transform the list into a circular list
    ptr->next->next = *head;
 
    // Fix the head pointer
    *head = ptr->next;
 
    // break the chain
    ptr->next= NULL;
}

function to reverse a list

int main ()
{
  std::list<int> mylist;


  for (int i=1; i<10; ++i) mylist.push_back(i);


  mylist.reverse();


  std::cout << "mylist contains:";
  for (std::list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it)
    std::cout << ' ' << *it;


  std::cout << '\n';


  return 0;
}

function to remove duplicate nodes 

Node *removeDuplicate(Node* head){
	//temp pointing to head
	Node *temp = head;            
	while(temp->next != NULL && temp != NULL){
		//Duplicate Found
		if(temp->data == temp->next->data){      
			//DUplicate Removed
			temp -> next = temp ->next ->next;    
		}
		else{
			//No Duplicate Present
			temp = temp->next;               
		}
	}
	//Return Head
	return head;                
}