Modify contents of Linked List | C ++ implementation to modify the contents of the linked list ; Linked list node ; Function to insert a node at the beginning of the linked list ; allocate node ; put in the data ; link the old list at the end of the new node ; move the head to point to the new node ; Split the nodes of the given list into front and back halves , and return the two lists using the reference parameters . Uses the fast / slow pointer strategy . ; Advance ' fast ' two nodes , and advance ' slow ' one node ; ' slow ' is before the midpoint in the list , so split it in two at that point . ; Function to reverse the linked list ; perfrom the required subtraction operation on the 1 st half of the linked list ; traversing both the lists simultaneously ; subtraction operation and node data modification ; function to concatenate the 2 nd ( back ) list at the end of the 1 st ( front ) list and returns the head of the new list ; function to modify the contents of the linked list ; if list is empty or contains only single node ; split the list into two halves front and back lists ; reverse the 2 nd ( back ) list ; modify the contents of 1 st half ; agains reverse the 2 nd ( back ) list ; concatenating the 2 nd list back to the end of the 1 st list ; pointer to the modified list ; function to print the linked list ; Driver program to test above ; creating the linked list ; modify the linked list ; print the modified linked list
#include <bits/stdc++.h> NEW_LINE using namespace std ; void printList ( struct Node * ) ; struct Node { int data ; struct Node * next ; } ; void push ( struct Node * * head_ref , int new_data ) { struct Node * new_node = ( struct Node * ) malloc ( sizeof ( struct Node ) ) ; new_node -> data = new_data ; new_node -> next = * head_ref ; * head_ref = new_node ; } void frontAndBackSplit ( struct Node * head , struct Node * * front_ref , struct Node * * back_ref ) { Node * slow , * fast ; slow = head ; fast = head -> next ; while ( fast != NULL ) { fast = fast -> next ; if ( fast != NULL ) { slow = slow -> next ; fast = fast -> next ; } } * front_ref = head ; * back_ref = slow -> next ; slow -> next = NULL ; } void reverseList ( struct Node * * head_ref ) { struct Node * current , * prev , * next ; current = * head_ref ; prev = NULL ; while ( current != NULL ) { next = current -> next ; current -> next = prev ; prev = current ; current = next ; } * head_ref = prev ; } void modifyTheContentsOf1stHalf ( struct Node * front , struct Node * back ) { while ( back != NULL ) { front -> data = front -> data - back -> data ; front = front -> next ; back = back -> next ; } } struct Node * concatFrontAndBackList ( struct Node * front , struct Node * back ) { struct Node * head = front ; while ( front -> next != NULL ) front = front -> next ; front -> next = back ; return head ; } struct Node * modifyTheList ( struct Node * head ) { if ( ! head head -> next == NULL ) return head ; struct Node * front , * back ; frontAndBackSplit ( head , & front , & back ) ; reverseList ( & back ) ; modifyTheContentsOf1stHalf ( front , back ) ; reverseList ( & back ) ; head = concatFrontAndBackList ( front , back ) ; return head ; } void printList ( struct Node * head ) { if ( ! head ) return ; while ( head -> next != NULL ) { cout << head -> data << " ▁ - > ▁ " ; head = head -> next ; } cout << head -> data << endl ; } int main ( ) { struct Node * head = NULL ; push ( & head , 10 ) ; push ( & head , 7 ) ; push ( & head , 12 ) ; push ( & head , 8 ) ; push ( & head , 9 ) ; push ( & head , 2 ) ; head = modifyTheList ( head ) ; cout << " Modified ▁ List : " << endl ; printList ( head ) ; return 0 ; }