Given a Linked List of even number of nodes, the task is to generate a new Linked List such that it contains the maximum difference of squares of node values in decreasing order by including each node in a single pair.
Examples:
Input: 1 -> 6 -> 4 -> 3 -> 5 ->2
Output: 35 -> 21 -> 7
Explanation:
The difference between squares of 6 and 1 forms the first node with value 35.
The difference between squares of 5 and 2 forms the second node with value 21.
The difference between squares of 4 and 3 forms the third node with value 7.
Therefore, the formed LL is 35 -> 21 -> 7.Input: 2 -> 4 -> 5 -> 3 -> 7 -> 8 -> 9 -> 10
Output: 96 -> 72 -> 48 -> 24
Explanation:
The difference between squares of 10 and 2 forms the first node with value 96.
The difference between squares of 9 and 3 forms the second node with value 72.
The difference between squares of 8 and 4 forms the third node with value 48.
The difference between squares of 7 and 5 forms the fourth node with value 24.
Therefore, the formed LL is 96 -> 72 -> 48 -> 24.
Approach: The approach is to find the maximum value of a node and always make the difference between the largest and the smallest node value. So create a deque and insert all node’s value in it, and sort the deque. Now, access the largest and smallest values from both ends. Below are the steps:
- Create a deque and insert all values into the deque.
- Sort the deque to get the largest node value and smallest node value in constant time.
- Create another linked list having the value difference of square’s of the largest and the smallest values from the back and the front of the deque respectively.
- After each iteration, pop both the smallest and largest value from the deque.
- After the above steps, print the nodes of the new Linked List formed.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Linked list nodestruct Node { int data; struct Node* next;};// Function to push into Linked Listvoid 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; new_node->next = (*head_ref); // Move the head to point // to the new node (*head_ref) = new_node;}// Function to print the Linked Listvoid print(struct Node* head){ Node* curr = head; // Iterate until curr is NULL while (curr) { // Print the data cout << curr->data << " "; // Move to next curr = curr->next; }}// Function to create a new Node of// the Linked Liststruct Node* newNode(int x){ struct Node* temp = (struct Node*)malloc( sizeof(struct Node)); temp->data = x; temp->next = NULL; // Return the node created return temp;}// Function used to re-order liststruct Node* reorder(Node* head){ // Stores the node of LL deque<int> v; Node* curr = head; // Traverse the LL while (curr) { v.push_back(curr->data); curr = curr->next; } // Sort the deque sort(v.begin(), v.end()); // Node head1 stores the // head of the new Linked List Node* head1 = NULL; Node* prev = NULL; // Size of new LL int x = v.size() / 2; // Loop to make new LL while (x--) { int a = v.front(); int b = v.back(); // Difference of squares of // largest and smallest value int ans = pow(b, 2) - pow(a, 2); // Create node with value ans struct Node* temp = newNode(ans); if (head1 == NULL) { head1 = temp; prev = temp; } // Otherwise, update prev else { prev->next = temp; prev = temp; } // Pop the front and back node v.pop_back(); v.pop_front(); } // Return head of the new LL return head1;}// Driver Codeint main(){ struct Node* head = NULL; // Given Linked list push(&head, 6); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); // Function Call Node* temp = reorder(head); // Print the new LL formed print(temp); return 0;} |
Java
// Java program for the // above approachimport java.util.*;class GFG{// Linked list nodestatic class Node { int data; Node next;};static Node head ;// Function to push // into Linked Liststatic void push(int new_data){ // Allocate node Node new_node = new Node(); // Put in the data new_node.data = new_data; new_node.next = head; // Move the head to point // to the new node head = new_node;}// Function to print the// Linked Liststatic void print(Node head){ Node curr = head; // Iterate until curr // is null while (curr != null) { // Print the data System.out.print(curr.data + " "); // Move to next curr = curr.next; }}// Function to create a // new Node of the Linked Liststatic Node newNode(int x){ Node temp = new Node(); temp.data = x; temp.next = null; // Return the node // created return temp;}// Function used to re-order // liststatic Node reorder(Node head){ // Stores the node of LL Deque<Integer> v = new LinkedList<>(); Node curr = head; // Traverse the LL while (curr != null) { v.add(curr.data); curr = curr.next; } // Sort the deque // Collections.sort(v); // Node head1 stores the // head of the new Linked // List Node head1 = null; Node prev = null; // Size of new LL int x = v.size() / 2; // Loop to make new LL while ((x--) > 0) { int a = v.peek(); int b = v.getLast(); // Difference of squares of // largest and smallest value int ans = (int)(Math.pow(b, 2) - Math.pow(a, 2)); // Create node with value ans Node temp = newNode(ans); if (head1 == null) { head1 = temp; prev = temp; } // Otherwise, update prev else { prev.next = temp; prev = temp; } // Pop the front and // back node v.removeFirst(); v.removeLast(); } // Return head of the // new LL return head1;}// Driver Codepublic static void main(String[] args){ head = null; // Given Linked list push(6); push(5); push(4); push(3); push(2); push(1); // Function Call Node temp = reorder(head); // Print the new // LL formed print(temp);}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the # above approachfrom collections import deque# Linked list nodeclass Node: def __init__(self, x): self.data = x self.next = None# Function to push into Linked List# Function to push into Linked Listdef push(head_ref, new_data): new_node = Node(new_data) new_node.next = head_ref head_ref = new_node return head_ref# Function to print the Linked Listdef printt(head): curr = head # Iterate until curr # is None while (curr): # Print the data print(curr.data, end = " ") # Move to next curr = curr.next# Function used to re-order list# Function used to re-order listdef reorder(head): # Stores the node of LL arr = [] curr = head while curr: arr.append(curr.data) curr = curr.next arr = sorted(arr) # Sort the deque v = deque() for i in arr: v.append(i) # Node head1 stores the # head of the new Linked List head1 = None prev = None x = len(arr) // 2 while x: a = v.popleft() b = v.pop() # Difference of squares of # largest and smallest value ans = pow(b, 2) - pow(a, 2) temp = Node(ans) if head1 == None: head1 = temp prev = temp else: prev.next = temp prev = temp x -= 1 # Return head of the new LL return head1# Driver Codeif __name__ == '__main__': head = None # Given Linked list head = push(head, 6) head = push(head, 5) head = push(head, 4) head = push(head, 3) head = push(head, 2) head = push(head, 1) # Function Call temp = reorder(head) # Print the new LL formed printt(temp)# This code is contributed by Mohit kumar 29 |
C#
// C# program for the // above approachusing System;using System.Collections.Generic;class GFG{// Linked list nodepublic class Node { public int data; public Node next;};static Node head ;// Function to push // into Linked Liststatic void push(int new_data){ // Allocate node Node new_node = new Node(); // Put in the data new_node.data = new_data; new_node.next = head; // Move the head to point // to the new node head = new_node;}// Function to print the// Linked Liststatic void print(Node head){ Node curr = head; // Iterate until curr // is null while (curr != null) { // Print the data Console.Write(curr.data + " "); // Move to next curr = curr.next; }}// Function to create a // new Node of the Linked Liststatic Node newNode(int x){ Node temp = new Node(); temp.data = x; temp.next = null; // Return the node // created return temp;}// Function used to re-order // liststatic Node reorder(Node head){ // Stores the node of LL List<int> v = new List<int>(); Node curr = head; // Traverse the LL while (curr != null) { v.Add(curr.data); curr = curr.next; } // Sort the deque // Collections.sort(v); // Node head1 stores the // head of the new Linked // List Node head1 = null; Node prev = null; // Size of new LL int x = v.Count / 2; // Loop to make new LL while ((x--) > 0) { int a = v[0]; int b = v[v.Count-1]; // Difference of squares of // largest and smallest value int ans = (int)(Math.Pow(b, 2) - Math.Pow(a, 2)); // Create node with value ans Node temp = newNode(ans); if (head1 == null) { head1 = temp; prev = temp; } // Otherwise, update prev else { prev.next = temp; prev = temp; } // Pop the front and // back node v.RemoveAt(0); v.RemoveAt(v.Count - 1); } // Return head of the // new LL return head1;}// Driver Codepublic static void Main(String[] args){ head = null; // Given Linked list push(6); push(5); push(4); push(3); push(2); push(1); // Function Call Node temp = reorder(head); // Print the new // LL formed print(temp);}}// This code is contributed by gauravrajput1 |
Javascript
<script>// javascript program for the // above approach // Linked list node class Node { constructor(val) { this.data = val; this.next = null; } } var head; // Function to push // into Linked List function push(new_data) { // Allocate node var new_node = new Node(); // Put in the data new_node.data = new_data; new_node.next = head; // Move the head to point // to the new node head = new_node; } // Function to print the // Linked List function print(head) { var curr = head; // Iterate until curr // is null while (curr != null) { // Print the data document.write(curr.data + " "); // Move to next curr = curr.next; } } // Function to create a // new Node of the Linked List function newNode(x) { var temp = new Node(); temp.data = x; temp.next = null; // Return the node // created return temp; } // Function used to re-order // list function reorder(head) { // Stores the node of LL var v = []; var curr = head; // Traverse the LL while (curr != null) { v.push(curr.data); curr = curr.next; } // Sort the deque // Collections.sort(v); // Node head1 stores the // head of the new Linked // List var head1 = null; var prev = null; // Size of new LL var x = v.length / 2; // Loop to make new LL while ((x--) > 0) { var a = v[0]; var b = v[v.length-1]; // Difference of squares of // largest and smallest value var ans = parseInt( (Math.pow(b, 2) - Math.pow(a, 2))); // Create node with value ans var temp = newNode(ans); if (head1 == null) { head1 = temp; prev = temp; } // Otherwise, update prev else { prev.next = temp; prev = temp; } // Pop the front and // back node v.pop(); v.shift(); } // Return head of the // new LL return head1; } // Driver Code head = null; // Given Linked list push(6); push(5); push(4); push(3); push(2); push(1); // Function Call var temp = reorder(head); // Print the new // LL formed print(temp);// This code is contributed by todaysgaurav</script> |
Output:
35 21 7
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
