Given a non-decreasing linked list. The task is to square the elements of the linked list and arrange them in sorted order without using any extra space.
Examples:
Input: 1->2->3->4->5
Output: 1->4->9->16->25Input: (-2) -> (-1) -> 0 -> 1 -> 2
Output: 0 ->1 -> 1 -> 4 -> 4
For Arrays: The problem to do the same for Arrays is discussed in this article – Sort array after converting elements to their squares
Approach: The task can be solved by partitioning the given list into two different linked lists from the point of transition (negative to positive), one containing only negative elements say ‘l1‘ and the other containing positive elements say ‘l2‘. Square all the elements of the list l1 and reverse it and also square all the elements of list l2, now merge the two sorted lists to get the resultant list.
Below is the implementation of the above approach :
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;struct Node { int data; Node* next; Node(int data) { this->data = data; this->next = NULL; }};// Utility function to make linked listNode* makeList(int n, int arr[]){ Node* h = NULL; Node* root; for (int i = 0; i < n; i++) { int data = arr[i]; Node* node = new Node(data); if (h == NULL) { h = node; root = h; } else { root->next = node; root = node; } } return h;}// Utility function to print listvoid print_list(Node* head){ while (head != NULL) { cout << head->data << " "; head = head->next; } cout << "\n";}// Function to reverse the linked listNode* reverse(Node* head){ // Initialize current, previous and // next pointers Node* current = head; Node *prev = NULL, *next = NULL; while (current != NULL) { // Store next next = current->next; // Reverse current node's pointer current->next = prev; // Move pointers one position ahead. prev = current; current = next; } head = prev; return head;}// This function will find the point of transition// where elements switch from negative to positive// and return that pointNode* findBreakPoint(Node* head){ if (head == NULL) { return NULL; } Node *prev = NULL, *curr = head; while (curr != NULL) { prev = curr; curr = curr->next; if (curr != NULL) { // If prev element is negative and // current element is positive if ((prev->data) < 0 and (curr->data) >= 0) { return prev; } } } // Checking if list contains // only negative elements curr = head; while (curr->next) { if (curr->data < 0) { curr = curr->next; continue; } else { // Contains positive elements return NULL; } } // Contains only negative element // so returning the last element of the list return curr;}// Utility function to merge two sorted listsstruct Node* mergeUtil(struct Node* h1, struct Node* h2){ // If only one node in first list // simply point its head to second list if (!h1->next) { h1->next = h2; return h1; } // Initialize current and next pointers of // both lists struct Node *curr1 = h1, *next1 = h1->next; struct Node *curr2 = h2, *next2 = h2->next; while (next1 && curr2) { // If curr2 lies in between // curr1 and next1 // then do curr1->curr2->next1 if ((curr2->data) >= (curr1->data) && (curr2->data) <= (next1->data)) { next2 = curr2->next; curr1->next = curr2; curr2->next = next1; // Let curr1 and curr2 to point // their immediate next pointers curr1 = curr2; curr2 = next2; } else { // If more nodes in first list if (next1->next) { next1 = next1->next; curr1 = curr1->next; } // Else point the last // node of first list // to the remaining // nodes of second list else { next1->next = curr2; return h1; } } } return h1;}// Merges two given lists in-place.// This function mainly compares// head nodes and calls mergeUtil()struct Node* merge(struct Node* h1, struct Node* h2){ if (!h1) return h2; if (!h2) return h1; // Start with the linked list // whose head data is the least if (h1->data < h2->data) return mergeUtil(h1, h2); else return mergeUtil(h2, h1);}// Function to return resultant squared listNode* squaresList(Node* head){ if (head == NULL) return NULL; Node* mid = findBreakPoint(head); Node* temp = head; while (temp != NULL) { temp->data *= temp->data; temp = temp->next; } // List contains only positive elements if (mid == NULL) { return head; } // List contains both positive // and negative elements Node* h1 = head; Node* h2 = mid->next; // Breaking the list where negative // switches to positive mid->next = NULL; // Reversing the list h1 = reverse(h1); // Merging the two lists Node* ans = merge(h1, h2); return ans;}// Driver Programint main(){ int n = 7; int arr1[] = { 1, 2, 3, 4, 5 }; Node* head = makeList(sizeof(arr1) / sizeof(int), arr1); n = 6; int arr2[] = { -2, -1, 0, 1, 2 }; head = makeList(sizeof(arr2) / sizeof(int), arr2); int arr3[] = { -5, -4, -3, -2, -1 }; head = makeList(sizeof(arr3) / sizeof(int), arr3); print_list(squaresList(head));} |
Java
// Java program for the above approachimport java.util.*;public class GFG{public static class Node { int data; Node next; Node(int data) { this.data = data; this.next = null; } public Node() { // TODO Auto-generated constructor stub }};// Utility function to make linked liststatic Node makeList(int n, int arr[]){ Node h = null; Node root = new Node(); for (int i = 0; i < n; i++) { int data = arr[i]; Node node = new Node(data); if (h == null) { h = node; root = h; } else { root.next = node; root = node; } } return h;}// Utility function to print liststatic void print_list(Node head){ while (head != null) { System.out.print(head.data+ " "); head = head.next; } System.out.print("\n");}// Function to reverse the linked liststatic Node reverse(Node head){ // Initialize current, previous and // next pointers Node current = head; Node prev = null, next = null; while (current != null) { // Store next next = current.next; // Reverse current node's pointer current.next = prev; // Move pointers one position ahead. prev = current; current = next; } head = prev; return head;}// This function will find the point of transition// where elements switch from negative to positive// and return that pointstatic Node findBreakPoint(Node head){ if (head == null) { return null; } Node prev = null, curr = head; while (curr != null) { prev = curr; curr = curr.next; if (curr != null) { // If prev element is negative and // current element is positive if ((prev.data) < 0 && (curr.data) >= 0) { return prev; } } } // Checking if list contains // only negative elements curr = head; while (curr.next!=null) { if (curr.data < 0) { curr = curr.next; continue; } else { // Contains positive elements return null; } } // Contains only negative element // so returning the last element of the list return curr;}// Utility function to merge two sorted listsstatic Node mergeUtil(Node h1, Node h2){ // If only one node in first list // simply point its head to second list if (h1.next!=null) { h1.next = h2; return h1; } // Initialize current and next pointers of // both lists Node curr1 = h1, next1 = h1.next; Node curr2 = h2, next2 = h2.next; while (next1!=null && curr2!=null) { // If curr2 lies in between // curr1 and next1 // then do curr1.curr2.next1 if ((curr2.data) >= (curr1.data) && (curr2.data) <= (next1.data)) { next2 = curr2.next; curr1.next = curr2; curr2.next = next1; // Let curr1 and curr2 to point // their immediate next pointers curr1 = curr2; curr2 = next2; } else { // If more nodes in first list if (next1.next!=null) { next1 = next1.next; curr1 = curr1.next; } // Else point the last // node of first list // to the remaining // nodes of second list else { next1.next = curr2; return h1; } } } return h1;}// Merges two given lists in-place.// This function mainly compares// head nodes and calls mergeUtil()static Node merge(Node h1, Node h2){ if (h1==null) return h2; if (h2==null) return h1; // Start with the linked list // whose head data is the least if (h1.data < h2.data) return mergeUtil(h1, h2); else return mergeUtil(h2, h1);}// Function to return resultant squared liststatic Node squaresList(Node head){ if (head == null) return null; Node mid = findBreakPoint(head); Node temp = head; while (temp != null) { temp.data *= temp.data; temp = temp.next; } // List contains only positive elements if (mid == null) { return head; } // List contains both positive // and negative elements Node h1 = head; Node h2 = mid.next; // Breaking the list where negative // switches to positive mid.next = null; // Reversing the list h1 = reverse(h1); // Merging the two lists Node ans = merge(h1, h2); return ans;}// Driver Programpublic static void main(String[] args){ int n = 7; int arr1[] = { 1, 2, 3, 4, 5 }; Node head = makeList(arr1.length, arr1); n = 6; int arr2[] = { -2, -1, 0, 1, 2 }; head = makeList(arr2.length, arr2); int arr3[] = { -5, -4, -3, -2, -1 }; head = makeList(arr3.length, arr3); print_list(squaresList(head));}}// This code is contributed by 29AjayKumar |
Python3
# Python program to implement# the above approachclass Node: def __init__(self, data=None, next=None): self.data = data self.next = nextdef make_list(n, arr): if n == 0: return None head = Node(arr[0]) curr = head for i in range(1, n): curr.next = Node(arr[i]) curr = curr.next return head# Utility function to print listdef print_list(head): while head is not None: print(head.data, end=" ") head = head.next print()# Function to reverse the linked listdef reverse(head): # Initialize current, previous and next pointers current = head prev = None next = None while current is not None: # Store next next = current.next # Reverse current node's pointer current.next = prev # Move pointers one position ahead. prev = current current = next head = prev return head# This function will find the point of transition# where elements switch from negative to positive# and return that pointdef find_break_point(head): if head is None: return None prev = None curr = head while curr is not None: prev = curr curr = curr.next if curr is not None: # If prev element is negative and # current element is positive if (prev.data < 0 and curr.data >= 0): return prev # Checking if list contains # only negative elements curr = head while curr.next: if curr.data < 0: curr = curr.next continue else: # Contains positive elements return None # Contains only negative element # so returning the last element of the list return curr# Utility function to merge two sorted listsdef mergeUtil(h1, h2): # If only one node in first list # simply point its head to second list if not h1.next: h1.next = h2 return h1 # Initialize current and next pointers of # both lists curr1 = h1 next1 = h1.next curr2 = h2 next2 = h2.next while next1 and curr2: # If curr2 lies in between # curr1 and next1 # then do curr1.curr2.next1 if curr2.data >= curr1.data and curr2.data <= next1.data: next2 = curr2.next curr1.next = curr2 curr2.next = next1 # Let curr1 and curr2 to point # their immediate next pointers curr1 = curr2 curr2 = next2 else: # If more nodes in first list if next1.next: next1 = next1.next curr1 = curr1.next # Else point the last # node of first list # to the remaining # nodes of second list else: next1.next = curr2 return h1 return h1# Merges two given lists in-place.# This function mainly compares# head nodes and calls merge_util()def merge(h1, h2): if not h1: return h2 if not h2: return h1 # Start with the linked list # whose head data is the least if h1.data < h2.data: return merge_util(h1, h2) else: return merge_util(h2, h1)# Function to return resultant squared listdef squares_list(head): if not head: return None mid = find_break_point(head) temp = head while temp: temp.data *= temp.data temp = temp.next # List contains only positive elements if not mid: return head # List contains both positive # and negative elements h1 = head h2 = mid.next # Breaking the list where negative # switches to positive mid.next = None # Reversing the list h1 = reverse(h1) # Merging the two lists ans = merge(h1, h2) return ans# Driver Programn = 7arr1 = [1, 2, 3, 4, 5]head = make_list(len(arr1), arr1)n = 6arr2 = [-2, -1, 0, 1, 2]head = make_list(len(arr2), arr2)arr3 = [-5, -4, -3, -2, -1]head = make_list(len(arr3), arr3)print_list(squares_list(head)) |
C#
// C# program for the above approachusing System;public class GFG{class Node { public int data; public Node next; public Node(int data) { this.data = data; this.next = null; } public Node() { // TODO Auto-generated constructor stub }};// Utility function to make linked liststatic Node makeList(int n, int []arr){ Node h = null; Node root = new Node(); for (int i = 0; i < n; i++) { int data = arr[i]; Node node = new Node(data); if (h == null) { h = node; root = h; } else { root.next = node; root = node; } } return h;}// Utility function to print liststatic void print_list(Node head){ while (head != null) { Console.Write(head.data+ " "); head = head.next; } Console.Write("\n");}// Function to reverse the linked liststatic Node reverse(Node head){ // Initialize current, previous and // next pointers Node current = head; Node prev = null, next = null; while (current != null) { // Store next next = current.next; // Reverse current node's pointer current.next = prev; // Move pointers one position ahead. prev = current; current = next; } head = prev; return head;}// This function will find the point of transition// where elements switch from negative to positive// and return that pointstatic Node findBreakPoint(Node head){ if (head == null) { return null; } Node prev = null, curr = head; while (curr != null) { prev = curr; curr = curr.next; if (curr != null) { // If prev element is negative and // current element is positive if ((prev.data) < 0 && (curr.data) >= 0) { return prev; } } } // Checking if list contains // only negative elements curr = head; while (curr.next!=null) { if (curr.data < 0) { curr = curr.next; continue; } else { // Contains positive elements return null; } } // Contains only negative element // so returning the last element of the list return curr;}// Utility function to merge two sorted listsstatic Node mergeUtil(Node h1, Node h2){ // If only one node in first list // simply point its head to second list if (h1.next!=null) { h1.next = h2; return h1; } // Initialize current and next pointers of // both lists Node curr1 = h1, next1 = h1.next; Node curr2 = h2, next2 = h2.next; while (next1!=null && curr2!=null) { // If curr2 lies in between // curr1 and next1 // then do curr1.curr2.next1 if ((curr2.data) >= (curr1.data) && (curr2.data) <= (next1.data)) { next2 = curr2.next; curr1.next = curr2; curr2.next = next1; // Let curr1 and curr2 to point // their immediate next pointers curr1 = curr2; curr2 = next2; } else { // If more nodes in first list if (next1.next!=null) { next1 = next1.next; curr1 = curr1.next; } // Else point the last // node of first list // to the remaining // nodes of second list else { next1.next = curr2; return h1; } } } return h1;}// Merges two given lists in-place.// This function mainly compares// head nodes and calls mergeUtil()static Node merge(Node h1, Node h2){ if (h1==null) return h2; if (h2==null) return h1; // Start with the linked list // whose head data is the least if (h1.data < h2.data) return mergeUtil(h1, h2); else return mergeUtil(h2, h1);}// Function to return resultant squared liststatic Node squaresList(Node head){ if (head == null) return null; Node mid = findBreakPoint(head); Node temp = head; while (temp != null) { temp.data *= temp.data; temp = temp.next; } // List contains only positive elements if (mid == null) { return head; } // List contains both positive // and negative elements Node h1 = head; Node h2 = mid.next; // Breaking the list where negative // switches to positive mid.next = null; // Reversing the list h1 = reverse(h1); // Merging the two lists Node ans = merge(h1, h2); return ans;}// Driver Programpublic static void Main(String[] args){ int n = 7; int []arr1 = { 1, 2, 3, 4, 5 }; Node head = makeList(arr1.Length, arr1); n = 6; int []arr2 = { -2, -1, 0, 1, 2 }; head = makeList(arr2.Length, arr2); int []arr3 = { -5, -4, -3, -2, -1 }; head = makeList(arr3.Length, arr3); print_list(squaresList(head));}}// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript Program to implement // the above approach class Node { constructor(data) { this.data = data; this.next = null; } } // Utility function to make linked list function makeList(n, arr) { let h = null; let root; for (let i = 0; i < n; i++) { let data = arr[i]; let node = new Node(data); if (h == null) { h = node; root = h; } else { root.next = node; root = node; } } return h; } // Utility function to print list function print_list(head) { while (head != null) { document.write(head.data + " ") head = head.next; } document.write("<br>") } // Function to reverse the linked list function reverse(head) { // Initialize current, previous and // next pointers let current = head; let prev = null, next = null; while (current != null) { // Store next next = current.next; // Reverse current node's pointer current.next = prev; // Move pointers one position ahead. prev = current; current = next; } head = prev; return head; } // This function will find the point of transition // where elements switch from negative to positive // and return that point function findBreakPoint(head) { if (head == null) { return null; } let prev = null, curr = head; while (curr != null) { prev = curr; curr = curr.next; if (curr != null) { // If prev element is negative and // current element is positive if ((prev.data) < 0 && (curr.data) >= 0) { return prev; } } } // Checking if list contains // only negative elements curr = head; while (curr.next) { if (curr.data < 0) { curr = curr.next; continue; } else { // Contains positive elements return null; } } // Contains only negative element // so returning the last element of the list return curr; } // Utility function to merge two sorted lists function mergeUtil(h1, h2) { // If only one node in first list // simply point its head to second list if (!h1.next) { h1.next = h2; return h1; } // Initialize current and next pointers of // both lists let curr1 = h1, next1 = h1.next; let curr2 = h2, next2 = h2.next; while (next1 && curr2) { // If curr2 lies in between // curr1 and next1 // then do curr1.curr2.next1 if ((curr2.data) >= (curr1.data) && (curr2.data) <= (next1.data)) { next2 = curr2.next; curr1.next = curr2; curr2.next = next1; // Let curr1 and curr2 to point // their immediate next pointers curr1 = curr2; curr2 = next2; } else { // If more nodes in first list if (next1.next) { next1 = next1.next; curr1 = curr1.next; } // Else point the last // node of first list // to the remaining // nodes of second list else { next1.next = curr2; return h1; } } } return h1; } // Merges two given lists in-place. // This function mainly compares // head nodes and calls mergeUtil() function merge(h1, h2) { if (!h1) return h2; if (!h2) return h1; // Start with the linked list // whose head data is the least if (h1.data < h2.data) return mergeUtil(h1, h2); else return mergeUtil(h2, h1); } // Function to return resultant squared list function squaresList(head) { if (head == null) return null; let mid = findBreakPoint(head); let temp = head; while (temp != null) { temp.data *= temp.data; temp = temp.next; } // List contains only positive elements if (mid == null) { return head; } // List contains both positive // and negative elements let h1 = head; let h2 = mid.next; // Breaking the list where negative // switches to positive mid.next = null; // Reversing the list h1 = reverse(h1); // Merging the two lists let ans = merge(h1, h2); return ans; } // Driver Program let n = 7; let arr1 = [1, 2, 3, 4, 5]; let head = makeList(arr1.length, arr1); n = 6; let arr2 = [-2, -1, 0, 1, 2]; head = makeList(arr2.length, arr2); let arr3 = [-5, -4, -3, -2, -1]; head = makeList(arr3.length, arr3); print_list(squaresList(head)); // This code is contributed by Potta Lokesh </script> |
Output
1 4 9 16 25
Time complexity: O(N), N is the number of nodes
Auxiliary space: O(1)
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!
