Modify contents of Linked List

Last Updated : 10 Jan, 2023

Given a singly linked list containing n nodes. Modify the value of first half nodes such that 1st node’s new value is equal to the last node’s value minus first node’s current value, 2nd node’s new value is equal to the second last node’s value minus 2nd node’s current value, likewise for first half nodes. If n is odd then the value of the middle node remains unchanged.
(No extra memory to be used).

Examples:

Input : 10 -> 4 -> 5 -> 3 -> 6
Output : 4 -> 1 -> 5 -> 3 -> 6

Input : 2 -> 9 -> 8 -> 12 -> 7 -> 10
Output : -8 -> 2 -> -4 -> 12 -> 7 -> 10

Asked in Amazon Interview

Approach: The following steps are:

Split the list from the middle. Perform front and back split. If the number of elements is odd, the extra element should go in the 1st(front) list.
Reverse the 2nd(back) list.
Perform the required subtraction while traversing both list simultaneously.
Again reverse the 2nd list.
Concatenate the 2nd list back to the end of the 1st list.

Implementation:

C++

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

Java

// Java implementation to modify the contents  
// of the linked list 
class GFG 
{ 
      
/* Linked list node */
static class Node 
{ 
    int data; 
    Node next; 
}; 
  
/* Function to insert a node at the beginning  
of the linked list */
static Node push(Node head_ref, int new_data) 
{ 
    /* allocate node */
    Node new_node =new Node(); 
    /* put in the data */
    new_node.data = new_data; 
          
    /* link the old list at the end  
    of the new node */
    new_node.next = head_ref;  
          
    /* move the head to point to the new node */
    head_ref = new_node; 
      
    return head_ref; 
}  
  
static Node front,back; 
  
/* 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. */
static void frontAndBackSplit( Node head) 
{ 
    Node slow, fast; 
      
    slow = head; 
    fast = head.next; 
      
    /* Advance 'fast' two nodes, and  
    advance 'slow' one node */
    while (fast != null) 
    { 
        fast = fast.next; 
        if (fast != null) 
        { 
            slow = slow.next; 
            fast = fast.next; 
        } 
    } 
      
    /* 'slow' is before the midpoint in the list,  
        so split it in two at that point. */
    front = head; 
    back = slow.next; 
    slow.next = null; 
} 
  
/* Function to reverse the linked list */
static Node reverseList( Node head_ref) 
{ 
    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; 
    return head_ref; 
} 
  
// perform the required subtraction operation  
// on the 1st half of the linked list 
static void modifyTheContentsOf1stHalf() 
{ 
    Node front1 = front, back1 = back; 
    // traversing both the lists simultaneously 
    while (back1 != null) 
    { 
        // subtraction operation and node data 
        // modification 
        front1.data = front1.data - back1.data; 
          
        front1 = front1.next; 
        back1 = back1.next; 
    } 
} 
  
// function to concatenate the 2nd(back) list  
// at the end of the 1st(front) list and  
// returns the head of the new list 
static Node concatFrontAndBackList(Node front, 
                                   Node back) 
{ 
    Node head = front; 
      
    if(front == null)return back; 
      
    while (front.next != null) 
        front = front.next;  
          
    front.next = back; 
      
    return head; 
} 
  
// function to modify the contents of the linked list 
static Node modifyTheList( Node head) 
{ 
    // if list is empty or contains only single node 
    if (head == null || head.next == null) 
        return head; 
    front = null; back = null; 
      
    // split the list into two halves 
    // front and back lists 
    frontAndBackSplit(head); 
          
    // reverse the 2nd(back) list 
    back = reverseList(back); 
      
    // modify the contents of 1st half  
    modifyTheContentsOf1stHalf(); 
      
    // agains reverse the 2nd(back) list 
    back = reverseList(back); 
      
    // concatenating the 2nd list back to the  
    // end of the 1st list 
    head = concatFrontAndBackList(front, back); 
  
    // pointer to the modified list 
    return head; 
} 
  
// function to print the linked list 
static void printList( Node head) 
{ 
    if (head == null) 
        return; 
      
    while (head.next != null) 
    { 
        System.out.print(head.data + " -> "); 
        head = head.next; 
    } 
    System.out.println(head.data ); 
} 
  
// Driver Code 
public static void main(String args[]) 
{ 
    Node head = null; 
      
    // creating the linked list 
    head = push(head, 10); 
    head = push(head, 7); 
    head = push(head, 12); 
    head = push(head, 8); 
    head = push(head, 9); 
    head = push(head, 2); 
      
    // modify the linked list 
    head = modifyTheList(head); 
      
    // print the modified linked list 
    System.out.println( "Modified List:" ); 
    printList(head); 
} 
} 
  
// This code is contributed by Arnab Kundu 

Python3

# Python3 implementation to modify the contents  
# of the linked list 
  
# Linked list node  
class Node:  
      
    def __init__(self, data):  
        self.data = data  
        self.next = None
  
# Function to insert a node at the beginning  
# of the linked list  
def push(head_ref, new_data): 
  
    # allocate node  
    new_node =Node(0) 
      
    # put in the data  
    new_node.data = new_data 
          
    # link the old list at the end  
    #of the new node  
    new_node.next = head_ref  
          
    # move the head to point to the new node  
    head_ref = new_node 
      
    return head_ref 
  
front = None
back = None
  
# 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.  
def frontAndBackSplit( head): 
  
    global front 
    global back 
    slow = None
    fast = None
      
    slow = head 
    fast = head.next
      
    # Advance 'fast' two nodes, and  
    # advance 'slow' one node  
    while (fast != None): 
      
        fast = fast.next
        if (fast != None): 
            slow = slow.next
            fast = fast.next
  
    # 'slow' is before the midpoint in the list,  
    # so split it in two at that point.  
    front = head 
    back = slow.next
    slow.next = None
    return head 
  
# Function to reverse the linked list  
def reverseList( head_ref): 
  
    current = None
    prev = None
    next = None
    current = head_ref 
    prev = None
    while (current != None): 
      
        next = current.next
        current.next = prev 
        prev = current 
        current = next
      
    head_ref = prev 
    return head_ref 
  
# perform the required subtraction operation  
# on the 1st half of the linked list 
def modifyTheContentsOf1stHalf(): 
  
    global front 
    global back 
    front1 = front 
    back1 = back 
      
    # traversing both the lists simultaneously 
    while (back1 != None): 
      
        # subtraction operation and node data 
        # modification 
        front1.data = front1.data - back1.data 
          
        front1 = front1.next
        back1 = back1.next
      
# function to concatenate the 2nd(back) list  
# at the end of the 1st(front) list and  
# returns the head of the new list 
def concatFrontAndBackList( front, back): 
      
    head = front 
      
    if(front == None): 
        return back 
      
    while (front.next != None): 
        front = front.next
          
    front.next = back 
    return head 
  
# function to modify the contents of the linked list 
def modifyTheList( head): 
  
    global front 
    global back 
  
    # if list is empty or contains only single node 
    if (head == None or head.next == None): 
        return head 
    front = None
    back = None
      
    # split the list into two halves 
    # front and back lists 
    frontAndBackSplit(head) 
          
    # reverse the 2nd(back) list 
    back = reverseList(back) 
      
    # modify the contents of 1st half  
    modifyTheContentsOf1stHalf() 
      
    # agains reverse the 2nd(back) list 
    back = reverseList(back) 
      
    # concatenating the 2nd list back to the  
    # end of the 1st list 
    head = concatFrontAndBackList(front, back) 
  
    # pointer to the modified list 
    return head 
  
# function to print the linked list 
def printList( head): 
  
    if (head == None): 
        return
      
    while (head.next != None): 
      
        print(head.data , " -> ",end="") 
        head = head.next
      
    print(head.data ) 
  
# Driver Code 
  
head = None
      
# creating the linked list 
head = push(head, 10) 
head = push(head, 7) 
head = push(head, 12) 
head = push(head, 8) 
head = push(head, 9) 
head = push(head, 2) 
      
# modify the linked list 
head = modifyTheList(head) 
      
# print the modified linked list 
print( "Modified List:" ) 
printList(head) 
  
# This code is contributed by Arnab Kundu 

C#

// C# implementation to modify the  
// contents of the linked list 
using System; 
  
class GFG 
{ 
      
/* Linked list node */
public class Node 
{ 
    public int data; 
    public Node next; 
}; 
  
/* Function to insert a node at  
the beginning of the linked list */
static Node push(Node head_ref,  
                  int new_data) 
{ 
    /* allocate node */
    Node new_node = new Node(); 
      
    /* put in the data */
    new_node.data = new_data; 
          
    /* link the old list at the end  
    of the new node */
    new_node.next = head_ref;  
          
    /* move the head to point to the new node */
    head_ref = new_node; 
      
    return head_ref; 
}  
  
static Node front, back; 
  
/* 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. */
static void frontAndBackSplit( Node head) 
{ 
    Node slow, fast; 
      
    slow = head; 
    fast = head.next; 
      
    /* Advance 'fast' two nodes, and  
    advance 'slow' one node */
    while (fast != null) 
    { 
        fast = fast.next; 
        if (fast != null) 
        { 
            slow = slow.next; 
            fast = fast.next; 
        } 
    } 
      
    /* 'slow' is before the midpoint in the list,  
        so split it in two at that point. */
    front = head; 
    back = slow.next; 
    slow.next = null; 
} 
  
/* Function to reverse the linked list */
static Node reverseList(Node head_ref) 
{ 
    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; 
    return head_ref; 
} 
  
// perform the required subtraction operation  
// on the 1st half of the linked list 
static void modifyTheContentsOf1stHalf() 
{ 
    Node front1 = front, back1 = back; 
      
    // traversing both the lists simultaneously 
    while (back1 != null) 
    { 
        // subtraction operation and node data 
        // modification 
        front1.data = front1.data - back1.data; 
          
        front1 = front1.next; 
        back1 = back1.next; 
    } 
} 
  
// function to concatenate the 2nd(back) list  
// at the end of the 1st(front) list and  
// returns the head of the new list 
static Node concatFrontAndBackList(Node front, 
                                   Node back) 
{ 
    Node head = front; 
      
    if(front == null) 
        return back; 
      
    while (front.next != null) 
        front = front.next;  
          
    front.next = back; 
      
    return head; 
} 
  
// function to modify the contents of 
// the linked list 
static Node modifyTheList(Node head) 
{ 
    // if list is empty or contains  
    // only single node 
    if (head == null || head.next == null) 
        return head; 
    front = null; back = null; 
      
    // split the list into two halves 
    // front and back lists 
    frontAndBackSplit(head); 
          
    // reverse the 2nd(back) list 
    back = reverseList(back); 
      
    // modify the contents of 1st half  
    modifyTheContentsOf1stHalf(); 
      
    // agains reverse the 2nd(back) list 
    back = reverseList(back); 
      
    // concatenating the 2nd list back to the  
    // end of the 1st list 
    head = concatFrontAndBackList(front, back); 
  
    // pointer to the modified list 
    return head; 
} 
  
// function to print the linked list 
static void printList( Node head) 
{ 
    if (head == null) 
        return; 
      
    while (head.next != null) 
    { 
        Console.Write(head.data + " -> "); 
        head = head.next; 
    } 
    Console.WriteLine(head.data ); 
} 
  
// Driver Code 
public static void Main() 
{ 
    Node head = null; 
      
    // creating the linked list 
    head = push(head, 10); 
    head = push(head, 7); 
    head = push(head, 12); 
    head = push(head, 8); 
    head = push(head, 9); 
    head = push(head, 2); 
      
    // modify the linked list 
    head = modifyTheList(head); 
      
    // print the modified linked list 
    Console.WriteLine( "Modified List:" ); 
    printList(head); 
} 
} 
  
// This code is contributed by PrinciRaj1992 

Javascript

<script> 
  
      // JavaScript implementation to modify the 
      // contents of the linked list 
      /* Linked list node */
      class Node { 
        constructor() { 
          this.data = 0; 
          this.next = null; 
        } 
      } 
  
      /* Function to insert a node at 
       the beginning of the linked list */
       function push(head_ref, new_data) { 
        /* allocate node */
        var new_node = new Node(); 
  
        /* put in the data */
        new_node.data = new_data; 
  
        /* link the old list at the end 
    of the new node */
        new_node.next = head_ref; 
  
        /* move the head to point to the new node */
        head_ref = new_node; 
  
        return head_ref; 
      } 
  
      var front, back; 
  
      /* 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. */
      function frontAndBackSplit(head) { 
        var slow, fast; 
  
        slow = head; 
        fast = head.next; 
  
        /* Advance 'fast' two nodes, and 
    advance 'slow' one node */
        while (fast != null) { 
          fast = fast.next; 
          if (fast != null) { 
            slow = slow.next; 
            fast = fast.next; 
          } 
        } 
  
        /* 'slow' is before the midpoint in the list, 
        so split it in two at that point. */
        front = head; 
        back = slow.next; 
        slow.next = null; 
      } 
  
      /* Function to reverse the linked list */
      function reverseList(head_ref) { 
        var current, prev, next; 
        current = head_ref; 
        prev = null; 
        while (current != null) { 
          next = current.next; 
          current.next = prev; 
          prev = current; 
          current = next; 
        } 
        head_ref = prev; 
        return head_ref; 
      } 
  
      // perform the required subtraction operation 
      // on the 1st half of the linked list 
      function modifyTheContentsOf1stHalf() { 
        var front1 = front, 
          back1 = back; 
  
        // traversing both the lists simultaneously 
        while (back1 != null) { 
          // subtraction operation and node data 
          // modification 
          front1.data = front1.data - back1.data; 
  
          front1 = front1.next; 
          back1 = back1.next; 
        } 
      } 
  
      // function to concatenate the 2nd(back) list 
      // at the end of the 1st(front) list and 
      // returns the head of the new list 
      function concatFrontAndBackList(front, back) { 
        var head = front; 
  
        if (front == null) return back; 
  
        while (front.next != null) front = front.next; 
  
        front.next = back; 
  
        return head; 
      } 
  
      // function to modify the contents of 
      // the linked list 
      function modifyTheList(head) { 
        // if list is empty or contains 
        // only single node 
        if (head == null || head.next == null) return head; 
        front = null; 
        back = null; 
  
        // split the list into two halves 
        // front and back lists 
        frontAndBackSplit(head); 
  
        // reverse the 2nd(back) list 
        back = reverseList(back); 
  
        // modify the contents of 1st half 
        modifyTheContentsOf1stHalf(); 
  
        // agains reverse the 2nd(back) list 
        back = reverseList(back); 
  
        // concatenating the 2nd list back to the 
        // end of the 1st list 
        head = concatFrontAndBackList(front, back); 
  
        // pointer to the modified list 
        return head; 
      } 
  
      // function to print the linked list 
      function printList(head) { 
        if (head == null) return; 
  
        while (head.next != null) { 
          document.write(head.data + " -> "); 
          head = head.next; 
        } 
        document.write(head.data + "<br>"); 
      } 
  
      // Driver Code 
      var head = null; 
  
      // creating the linked list 
      head = push(head, 10); 
      head = push(head, 7); 
      head = push(head, 12); 
      head = push(head, 8); 
      head = push(head, 9); 
      head = push(head, 2); 
  
      // modify the linked list 
      head = modifyTheList(head); 
  
      // print the modified linked list 
      document.write("Modified List: <br>"); 
      printList(head); 
        
</script>

Output

Modified List:
-8 -> 2 -> -4 -> 12 -> 7 -> 10

Time Complexity: O(n), where n in the number of nodes.
Space complexity: O(1) since using constant space to modify pointers

Another approach (Using Stack) :

Find the starting point of second half Linked List.
Push all elements of second half list into stack s.
Traverse list starting from head using temp until stack is not empty and do Modify temp->data by subtracting the top element of stack for every node.

Below is the implementation using stack.

C++

// C++ implementation to modify the 
// contents of the linked list 
#include <bits/stdc++.h> 
using namespace std; 
  
// Linked list node 
struct Node 
{ 
    int data; 
    struct Node* next; 
}; 
  
// function prototype for printing the list 
void printList(struct Node*); 
  
// Function to insert a node at the 
// beginning of the linked list 
void push(struct Node **head_ref, int new_data) 
{ 
  
// allocate node 
struct Node* new_node = 
            (struct Node*) malloc(sizeof(struct Node)); 
  
// put in the data 
new_node->data = new_data; 
  
// link the old list at the end of the new node 
new_node->next = *head_ref;  
  
// move the head to point to the new node 
*head_ref = new_node; 
}  
  
// function to print the linked list 
void printList(struct Node *head) 
{ 
    if (!head) 
        return; 
      
    while (head->next != NULL) 
    { 
        cout << head->data << " -> "; 
        head = head->next; 
    } 
    cout << head->data << endl; 
} 
  
// Function to middle node of list. 
Node* find_mid(Node *head) 
{ 
    Node *temp = head, *slow = head, *fast = head ; 
      
    while(fast && fast->next) 
    { 
          
    // Advance 'fast' two nodes, and  
    // advance 'slow' one node 
    slow = slow->next ; 
    fast = fast->next->next ; 
    } 
      
    // If number of nodes are odd then update slow 
    // by slow->next; 
    if(fast) 
    slow = slow->next ; 
  
return slow ; 
} 
  
// function to modify the contents of the linked list. 
void modifyTheList(struct Node *head, struct Node *slow) 
{ 
// Create Stack.  
stack <int> s; 
Node *temp = head ; 
  
while(slow) 
{ 
    s.push( slow->data ) ; 
    slow = slow->next ; 
} 
  
// Traverse the list by using temp until stack is empty. 
while( !s.empty() ) 
{ 
    temp->data = temp->data - s.top() ; 
    temp = temp->next ; 
    s.pop() ; 
} 
  
} 
  
// Driver program to test above 
int main() 
{ 
    struct Node *head = NULL, *mid ; 
      
    // creating the linked list 
    push(&head, 10); 
    push(&head, 7); 
    push(&head, 12); 
    push(&head, 8); 
    push(&head, 9); 
    push(&head, 2); 
      
    // Call Function to Find the starting point of second half of list.  
    mid = find_mid(head) ; 
      
    // Call function to modify the contents of the linked list. 
    modifyTheList( head, mid); 
      
      
    // print the modified linked list 
    cout << "Modified List:" << endl; 
    printList(head); 
    return 0; 
}  
  
// This is contributed by Mr. Gera 

Java

// Java implementation to modify the 
// contents of the linked list 
import java.util.*; 
  
class GFG  
{ 
  
    // Linked list node 
    static class Node  
    { 
  
        int data; 
        Node next; 
    }; 
  
    // Function to insert a node at the 
    // beginning of the linked list 
    static Node push(Node head_ref, int new_data)  
    { 
  
        // allocate node 
        Node new_node = new Node(); 
  
        // put in the data 
        new_node.data = new_data; 
  
        // link the old list at the end of the new node 
        new_node.next = head_ref; 
  
        // move the head to point to the new node 
        head_ref = new_node; 
        return head_ref; 
    } 
  
    // function to print the linked list 
    static void printList(Node head)  
    { 
        if (head == null)  
        { 
            return; 
        } 
  
        while (head.next != null)  
        { 
            System.out.print(head.data + "->"); 
            head = head.next; 
        } 
        System.out.print(head.data + "\n"); 
    } 
  
    // Function to middle node of list. 
    static Node find_mid(Node head)  
    { 
        Node temp = head, slow = head, fast = head; 
  
        while (fast != null && fast.next != null) 
        { 
  
            // Advance 'fast' two nodes, and  
            // advance 'slow' one node 
            slow = slow.next; 
            fast = fast.next.next; 
        } 
  
        // If number of nodes are odd then update slow 
        // by slow.next; 
        if (fast != null)  
        { 
            slow = slow.next; 
        } 
  
        return slow; 
    } 
  
    // function to modify the contents of the linked list. 
    static void modifyTheList(Node head, Node slow)  
    { 
        // Create Stack.  
        Stack<Integer> s = new Stack<Integer>(); 
        Node temp = head; 
  
        while (slow != null)  
        { 
            s.add(slow.data); 
            slow = slow.next; 
        } 
  
    // Traverse the list by using temp until stack is empty. 
        while (!s.empty()) 
        { 
            temp.data = temp.data - s.peek(); 
            temp = temp.next; 
            s.pop(); 
        } 
  
    } 
  
    // Driver program to test above 
    public static void main(String[] args) 
    { 
        Node head = null, mid; 
  
        // creating the linked list 
        head = push(head, 10); 
        head = push(head, 7); 
        head = push(head, 12); 
        head = push(head, 8); 
        head = push(head, 9); 
        head = push(head, 2); 
  
        // Call Function to Find the starting 
        // point of second half of list.  
        mid = find_mid(head); 
  
        // Call function to modify  
        // the contents of the linked list. 
        modifyTheList(head, mid); 
  
        // print the modified linked list 
        System.out.print("Modified List:" + "\n"); 
        printList(head); 
    } 
} 
  
// This code is contributed by Rajput-Ji 

Python3

# Python3 implementation to modify the 
# contents of the linked list 
   
# Linked list node 
class Node: 
      
    def __init__(self): 
          
        self.data = 0
        self.next = None
   
# Function to insert a node at the 
# beginning of the linked list 
def append(head_ref, new_data): 
  
    # Allocate node 
    new_node = Node() 
      
    # Put in the data 
    new_node.data = new_data 
      
    # Link the old list at the end 
    # of the new node 
    new_node.next = head_ref  
      
    # Move the head to point to the new node 
    head_ref = new_node 
      
    return head_ref 
      
# Function to print the linked list 
def printList(head): 
  
    if (not head): 
        return; 
       
    while (head.next != None): 
        print(head.data, end = ' -> ') 
        head = head.next
      
    print(head.data) 
      
# Function to middle node of list. 
def find_mid(head): 
  
    temp = head 
    slow = head 
    fast = head  
       
    while (fast and fast.next): 
          
        # Advance 'fast' two nodes, and  
        # advance 'slow' one node 
        slow = slow.next 
        fast = fast.next.next 
          
    # If number of nodes are odd then  
    # update slow by slow.next; 
    if (fast): 
        slow = slow.next 
   
    return slow  
  
# Function to modify the contents of  
# the linked list. 
def modifyTheList(head, slow): 
  
    # Create Stack.  
    s = [] 
    temp = head  
      
    while (slow): 
        s.append(slow.data)  
        slow = slow.next 
  
    # Traverse the list by using  
    # temp until stack is empty. 
    while (len(s) != 0): 
        temp.data = temp.data - s[-1] 
        temp = temp.next 
        s.pop()  
      
# Driver code 
if __name__=='__main__': 
      
    head = None
       
    # creating the linked list 
    head = append(head, 10) 
    head = append(head, 7) 
    head = append(head, 12) 
    head = append(head, 8) 
    head = append(head, 9) 
    head = append(head, 2) 
       
    # Call Function to Find the  
    # starting point of second half of list.  
    mid = find_mid(head)  
       
    # Call function to modify the  
    # contents of the linked list. 
    modifyTheList( head, mid) 
       
    # Print the modified linked list 
    print("Modified List:") 
    printList(head) 
  
# This code is contributed by rutvik_56

C#

// C# implementation to modify the 
// contents of the linked list 
using System; 
using System.Collections.Generic; 
  
class GFG  
{ 
  
    // Linked list node 
    public class Node  
    { 
  
        public int data; 
        public Node next; 
    }; 
  
    // Function to insert a node at the 
    // beginning of the linked list 
    static Node push(Node head_ref, int new_data)  
    { 
  
        // allocate node 
        Node new_node = new Node(); 
  
        // put in the data 
        new_node.data = new_data; 
  
        // link the old list at the end of the new node 
        new_node.next = head_ref; 
  
        // move the head to point to the new node 
        head_ref = new_node; 
        return head_ref; 
    } 
  
    // function to print the linked list 
    static void printList(Node head)  
    { 
        if (head == null)  
        { 
            return; 
        } 
  
        while (head.next != null)  
        { 
            Console.Write(head.data + "->"); 
            head = head.next; 
        } 
        Console.Write(head.data + "\n"); 
    } 
  
    // Function to middle node of list. 
    static Node find_mid(Node head)  
    { 
        Node temp = head, slow = head, fast = head; 
  
        while (fast != null && fast.next != null) 
        { 
  
            // Advance 'fast' two nodes, and  
            // advance 'slow' one node 
            slow = slow.next; 
            fast = fast.next.next; 
        } 
  
        // If number of nodes are odd then update slow 
        // by slow.next; 
        if (fast != null)  
        { 
            slow = slow.next; 
        } 
  
        return slow; 
    } 
  
    // function to modify the contents of the linked list. 
    static void modifyTheList(Node head, Node slow)  
    { 
        // Create Stack.  
        Stack<int> s = new Stack<int>(); 
        Node temp = head; 
  
        while (slow != null)  
        { 
            s.Push(slow.data); 
            slow = slow.next; 
        } 
  
        // Traverse the list by using temp until stack is empty. 
        while (s.Count != 0) 
        { 
            temp.data = temp.data - s.Peek(); 
            temp = temp.next; 
            s.Pop(); 
        } 
  
    } 
  
    // Driver code 
    public static void Main(String[] args) 
    { 
        Node head = null, mid; 
  
        // creating the linked list 
        head = push(head, 10); 
        head = push(head, 7); 
        head = push(head, 12); 
        head = push(head, 8); 
        head = push(head, 9); 
        head = push(head, 2); 
  
        // Call Function to Find the starting 
        // point of second half of list.  
        mid = find_mid(head); 
  
        // Call function to modify  
        // the contents of the linked list. 
        modifyTheList(head, mid); 
  
        // print the modified linked list 
        Console.Write("Modified List:" + "\n"); 
        printList(head); 
    } 
} 
  
// This code is contributed by PrinciRaj1992 

Javascript

<script> 
  
// JavaScript implementation to modify the 
// contents of the linked list 
  
    // Linked list node 
class Node { 
    constructor(val) { 
        this.data = val; 
        this.next = null; 
    } 
} 
  
    // Function to insert a node at the 
    // beginning of the linked list 
    function push(head_ref , new_data) { 
  
        // allocate node 
        var new_node = new Node(); 
  
        // put in the data 
        new_node.data = new_data; 
  
        // link the old list at the end of the new node 
        new_node.next = head_ref; 
  
        // move the head to point to the new node 
        head_ref = new_node; 
        return head_ref; 
    } 
  
    // function to print the linked list 
    function printList(head) { 
        if (head == null) { 
            return; 
        } 
  
        while (head.next != null) { 
            document.write(head.data + "->"); 
            head = head.next; 
        } 
        document.write(head.data + "<br/>"); 
    } 
  
    // Function to middle node of list. 
    function find_mid(head) { 
    var temp = head, slow = head, fast = head; 
  
        while (fast != null && fast.next != null) { 
  
            // Advance 'fast' two nodes, and 
            // advance 'slow' one node 
            slow = slow.next; 
            fast = fast.next.next; 
        } 
  
        // If number of nodes are odd then update slow 
        // by slow.next; 
        if (fast != null) { 
            slow = slow.next; 
        } 
  
        return slow; 
    } 
  
    // function to modify the contents of the linked list. 
    function modifyTheList(head,  slow) { 
        // Create Stack. 
        var s = []; 
        var temp = head; 
  
        while (slow != null) { 
            s.push(slow.data); 
            slow = slow.next; 
        } 
  
        // Traverse the list by using temp until stack is empty. 
        while (s.length!=0) { 
            temp.data = temp.data - s.pop(); 
            temp = temp.next; 
              
        } 
  
    } 
  
    // Driver program to test above 
      
        var head = null, mid; 
  
        // creating the linked list 
        head = push(head, 10); 
        head = push(head, 7); 
        head = push(head, 12); 
        head = push(head, 8); 
        head = push(head, 9); 
        head = push(head, 2); 
  
        // Call Function to Find the starting 
        // point of second half of list. 
        mid = find_mid(head); 
  
        // Call function to modify 
        // the contents of the linked list. 
        modifyTheList(head, mid); 
  
        // print the modified linked list 
        document.write("Modified List:" + "<br/>"); 
        printList(head); 
  
// This code contributed by Rajput-Ji 
  
</script> 

Output

Modified List:
-8 -> 2 -> -4 -> 12 -> 7 -> 10

Time Complexity : O(n)
Space Complexity : O(n/2)

Suggest improvement

Remove every k-th node of the linked list

Smallest number S such that N is a factor of S factorial or S!

Share your thoughts in the comments

Modify contents of Linked List

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?