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++
#include <bits/stdc++.h>
using namespace std;
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 print( struct Node* head)
{
Node* curr = head;
while (curr) {
cout << curr->data << " " ;
curr = curr->next;
}
}
struct Node* newNode( int x)
{
struct Node* temp
= ( struct Node*) malloc (
sizeof ( struct Node));
temp->data = x;
temp->next = NULL;
return temp;
}
struct Node* reorder(Node* head)
{
deque< int > v;
Node* curr = head;
while (curr) {
v.push_back(curr->data);
curr = curr->next;
}
sort(v.begin(), v.end());
Node* head1 = NULL;
Node* prev = NULL;
int x = v.size() / 2;
while (x--) {
int a = v.front();
int b = v.back();
int ans = pow (b, 2) - pow (a, 2);
struct Node* temp = newNode(ans);
if (head1 == NULL) {
head1 = temp;
prev = temp;
}
else {
prev->next = temp;
prev = temp;
}
v.pop_back();
v.pop_front();
}
return head1;
}
int main()
{
struct Node* head = NULL;
push(&head, 6);
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
Node* temp = reorder(head);
print(temp);
return 0;
}
|
Java
import java.util.*;
class GFG{
static class Node
{
int data;
Node next;
};
static Node head ;
static void push( int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head;
head = new_node;
}
static void print(Node head)
{
Node curr = head;
while (curr != null )
{
System.out.print(curr.data + " " );
curr = curr.next;
}
}
static Node newNode( int x)
{
Node temp = new Node();
temp.data = x;
temp.next = null ;
return temp;
}
static Node reorder(Node head)
{
Deque<Integer> v =
new LinkedList<>();
Node curr = head;
while (curr != null )
{
v.add(curr.data);
curr = curr.next;
}
Node head1 = null ;
Node prev = null ;
int x = v.size() / 2 ;
while ((x--) > 0 )
{
int a = v.peek();
int b = v.getLast();
int ans = ( int )(Math.pow(b, 2 ) -
Math.pow(a, 2 ));
Node temp = newNode(ans);
if (head1 == null )
{
head1 = temp;
prev = temp;
}
else
{
prev.next = temp;
prev = temp;
}
v.removeFirst();
v.removeLast();
}
return head1;
}
public static void main(String[] args)
{
head = null ;
push( 6 );
push( 5 );
push( 4 );
push( 3 );
push( 2 );
push( 1 );
Node temp = reorder(head);
print(temp);
}
}
|
Python3
from collections import deque
class Node:
def __init__( self , x):
self .data = x
self . next = None
def push(head_ref, new_data):
new_node = Node(new_data)
new_node. next = head_ref
head_ref = new_node
return head_ref
def printt(head):
curr = head
while (curr):
print (curr.data,
end = " " )
curr = curr. next
def reorder(head):
arr = []
curr = head
while curr:
arr.append(curr.data)
curr = curr. next
arr = sorted (arr)
v = deque()
for i in arr:
v.append(i)
head1 = None
prev = None
x = len (arr) / / 2
while x:
a = v.popleft()
b = v.pop()
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 head1
if __name__ = = '__main__' :
head = None
head = push(head, 6 )
head = push(head, 5 )
head = push(head, 4 )
head = push(head, 3 )
head = push(head, 2 )
head = push(head, 1 )
temp = reorder(head)
printt(temp)
|
C#
using System;
using System.Collections.Generic;
class GFG{
public class Node
{
public int data;
public Node next;
};
static Node head ;
static void push( int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head;
head = new_node;
}
static void print(Node head)
{
Node curr = head;
while (curr != null )
{
Console.Write(curr.data + " " );
curr = curr.next;
}
}
static Node newNode( int x)
{
Node temp = new Node();
temp.data = x;
temp.next = null ;
return temp;
}
static Node reorder(Node head)
{
List< int > v =
new List< int >();
Node curr = head;
while (curr != null )
{
v.Add(curr.data);
curr = curr.next;
}
Node head1 = null ;
Node prev = null ;
int x = v.Count / 2;
while ((x--) > 0)
{
int a = v[0];
int b = v[v.Count-1];
int ans = ( int )(Math.Pow(b, 2) -
Math.Pow(a, 2));
Node temp = newNode(ans);
if (head1 == null )
{
head1 = temp;
prev = temp;
}
else
{
prev.next = temp;
prev = temp;
}
v.RemoveAt(0);
v.RemoveAt(v.Count - 1);
}
return head1;
}
public static void Main(String[] args)
{
head = null ;
push(6);
push(5);
push(4);
push(3);
push(2);
push(1);
Node temp = reorder(head);
print(temp);
}
}
|
Javascript
<script>
class Node {
constructor(val) {
this .data = val;
this .next = null ;
}
}
var head;
function push(new_data) {
var new_node = new Node();
new_node.data = new_data;
new_node.next = head;
head = new_node;
}
function print(head) {
var curr = head;
while (curr != null ) {
document.write(curr.data + " " );
curr = curr.next;
}
}
function newNode(x) {
var temp = new Node();
temp.data = x;
temp.next = null ;
return temp;
}
function reorder(head) {
var v = [];
var curr = head;
while (curr != null ) {
v.push(curr.data);
curr = curr.next;
}
var head1 = null ;
var prev = null ;
var x = v.length / 2;
while ((x--) > 0) {
var a = v[0];
var b = v[v.length-1];
var ans = parseInt( (Math.pow(b, 2) - Math.pow(a, 2)));
var temp = newNode(ans);
if (head1 == null ) {
head1 = temp;
prev = temp;
}
else {
prev.next = temp;
prev = temp;
}
v.pop();
v.shift();
}
return head1;
}
head = null ;
push(6);
push(5);
push(4);
push(3);
push(2);
push(1);
var temp = reorder(head);
print(temp);
</script>
|
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 geeks!