Generate Linked List consisting of maximum difference of squares of pairs of nodes from given Linked List

0 0 9 minutes read

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 node
struct Node {
    int data;
    struct Node* next;
};
 
// Function to push into 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;
    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 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 List
struct 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 list
struct 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 Code
int 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 approach
import java.util.*;
class GFG{
 
// Linked list node
static class Node 
{
  int data;
  Node next;
};
 
static Node head ;
 
// Function to push 
// into Linked List
static 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 List
static 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 List
static 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 
// list
static 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 Code
public 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 approach
from collections import deque
 
# Linked list node
class Node:
   
    def __init__(self, x):
       
        self.data = x
        self.next = None
 
# Function to push into Linked List
# Function to push into Linked List
def 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 List
def 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 list
def 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 Code
if __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 approach
using System;
using System.Collections.Generic;
class GFG{
 
// Linked list node
public class Node 
{
  public int data;
  public Node next;
};
 
static Node head ;
 
// Function to push 
// into Linked List
static 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 List
static 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 List
static 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 
// list
static 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 Code
public 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 zambiatek!