Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!
Basic Pointer Manipulation

Arrange the Salary

Deepanshu

Last Updated on June 17, 2022 by Ria Pathak

CONCEPTS USED:

Basic Pointer Manipulation

DIFFICULTY LEVEL:

Medium

PROBLEM STATEMENT(SIMPLIFIED):

Given a linked list of N elements and a value X, your task is to arrange the list in such a way that all elements less than X comes first, then finally all elements greater than or equal to X.

NOTE : You have to maintain the original relative order of the elements at the time of arranging the salary.

See original problem statement here

For Example:

Input :  

list = 9 -> 6 -> 3 -> 7 -> 1 -> 4
K = 5

Output: 3 -> 1 -> 4 -> 9 -> 6 -> 7

Explaination : Elements smaller than 5 i.e. 3, 1, 4 are arranged at the starting while elements greater than 5 are arranged after them without changing the relative order of all the elements.

SOLVING APPROACH:

BRUTE FORCE METHOD:

  1. The idea is to create two additional arrays min_arr and max_arr for storing the elements less than X in min_arr while to store elements greater than or equal to X in max_arr.
  2. Then simply print elements from min_arr first and then max_arr.
  3. This approach is not efficient as it uses additional O(N) space.

SOLUTIONS:


#include <bits/stdc++.h>
using namespace std;
typedef struct Node {
    int data;
    struct Node *next;
}Node;
Node* temp = NULL;
Node* insert(Node *head, int data) {
    if(head == NULL) {
        head = new Node();
        head->data = data;
        head->next = NULL;
        return temp = head;
    }
    Node* node = new Node();
    node->data = data;
    node->next = NULL;
    temp->next = node;
    temp = temp->next;
    return head;
}

void print(Node *head) {
    if(head->next == NULL) {
        cout << head->data << " ";
        return;
    }
    cout << head->data << " ";
    print(head->next);
}

Node* ArrangeSalary(Node* head, int X) {

    if(head == NULL || head->next == NULL)
      return head;

    Node *temp = head;

    vector<int> v_min, v_max;
    while(temp != NULL){
      if(temp->data < X)
        v_min.push_back(temp->data);
      else
        v_max.push_back(temp->data);
      temp = temp->next;
    }

    temp = head;

    while(temp != NULL){
      if(!v_min.empty()){
        temp->data = v_min.front();
        v_min.erase(v_min.begin());
      }
      else if(!v_max.empty()){
        temp->data = v_max.front();
        v_max.erase(v_max.begin());
      }

      temp = temp->next;
    }
    return head;

}

int main()
{

    Node *head = NULL;
    Node *ptr = NULL;
    int n, X;
    cin >> n >>X;
    for(int i=0; i<n; i++) {
        int data;
        cin >> data;
        head = insert(head, data);
    }
    head = ArrangeSalary(head, X);
    print(head);
    cout << endl;
    return 0;
}

EFFICIENT METHOD:

  1. The idea is to create two linked list and initialize their head nodes as NULL –

    • smaller list of values smaller than X.
    • larger list of values greater than or equal to X.

  2. Now traverse the original list and if an element is less than X, append it to the end of the smaller list else append it to the end of the larger list. Finally concatenate both the smaller and larger lists to form the resultant list.

SOLUTIONS:


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct Node {
    int data;
    struct Node *next;
}Node;
Node* getNode (Node*head, int val)
{
    Node *element = (Node*) malloc(sizeof(Node));
    element->data = val ;
    element->next = NULL ;
    Node *temp = head ;
    if ( head == NULL ) {
        head = element ;
        head->next = NULL ;
        return head ;
    }
    while (temp->next != NULL)
        temp = temp->next ;
    temp->next = element ;
    element->next = NULL ;
    return head ;
}


void print(Node *head) {
    if(head->next == NULL) {
        printf("%d ", head->data);
        return;
    }
    printf("%d ", head->data);
    print(head->next);
}

Node* ArrangeSalary(Node* head, int X) {

  /* if list has 0 or 1 elements then return */
  if(head == NULL || head->next == NULL)
    return head;

  /* create two lists one for storing smaller elements than X and
    another for storing greater than or equal to elements than X */

  /* head pointer for smaller list */
  Node *smaller = NULL ;

  /*pointer to the last element in the smaller list */
  Node *temp_smaller;

   /* head pointer for greater list */
  Node *greater = NULL ;

  /*pointer to the last element in the greater list */
  Node *temp_greater ;

  Node *temp = head;

  while(temp != NULL){
    Node* t = temp;
    temp = temp -> next;

    if(t->data < X){
      if(smaller == NULL){
        smaller = t;
        temp_smaller = t;
        t -> next = NULL;
      }
      else{
        temp_smaller -> next = t;
        t -> next = NULL;
        temp_smaller = t;
      }

    }
    else{
      if(greater == NULL){
        greater = t;
        temp_greater = t;
        t -> next = NULL;
      }
      else{
        temp_greater -> next = t;
        t -> next = NULL;
        temp_greater = t;
      }
    }
  }

  /* concatenating both smaller and greater lists */
  temp_smaller -> next = greater;

  return smaller;

}
int main()
{

    Node *head = NULL;
    int n, X;
    scanf("%d %d", &n,&X);
    for(int i=0; i<n; i++) {
        int data;
        scanf("%d", &data);
        head = getNode(head, data);
    }
    head = ArrangeSalary(head, X);
    print(head);
    printf("\n");
    return 0;
}


#include <bits/stdc++.h>
using namespace std;
typedef struct Node {
    int data;
    struct Node *next;
}Node;
Node* temp = NULL;
Node* insert(Node *head, int data) {
    if(head == NULL) {
        head = new Node();
        head->data = data;
        head->next = NULL;
        return temp = head;
    }
    Node* node = new Node();
    node->data = data;
    node->next = NULL;
    temp->next = node;
    temp = temp->next;
    return head;
}

void print(Node *head) {
    if(head->next == NULL) {
        cout << head->data << " ";
        return;
    }
    cout << head->data << " ";
    print(head->next);
}

Node* ArrangeSalary(Node* head, int X) {

  /* if list has 0 or 1 elements then return */
  if(head == NULL || head->next == NULL)
    return head;

  /* create two lists one for storing smaller elements than X and
    another for storing greater than or equal to elements than X */

  /* head pointer for smaller list */
  Node *smaller = NULL ;

  /*pointer to the last element in the smaller list */
  Node *temp_smaller= NULL;

   /* head pointer for greater list */
  Node *greater = NULL ;

  /*pointer to the last element in the greater list */
  Node *temp_greater = NULL;

  Node *temp = head;

  while(temp != NULL){
    Node* t = temp;
    temp = temp -> next;

    if(t->data < X){
      if(smaller == NULL){
        smaller = t;
        temp_smaller = t;
        t -> next = NULL;
      }
      else{
        temp_smaller -> next = t;
        t -> next = NULL;
        temp_smaller = t;
      }

    }
    else{
      if(greater == NULL){
        greater = t;
        temp_greater = t;
        t -> next = NULL;
      }
      else{
        temp_greater -> next = t;
        t -> next = NULL;
        temp_greater = t;
      }
    }
  }

  /* concatenating both smaller and greater lists */
  temp_smaller -> next = greater;

  return smaller;
}

int main()
{

    Node *head = NULL;
    Node *ptr = NULL;
    int n, X;
    cin >> n >>X;
    for(int i=0; i<n; i++) {
        int data;
        cin >> data;
        head = insert(head, data);
    }
    head = ArrangeSalary(head, X);
    print(head);
    cout << endl;
    return 0;
}


import java.io.*;
import java.util.*;

public class Main {
    static class SinglyLinkedListNode {
        public int value;
        public SinglyLinkedListNode next;

        public SinglyLinkedListNode(int nodeData) {
            this.value = nodeData;
            this.next = null;
        }
    }

    static class SinglyLinkedList {
        public SinglyLinkedListNode head;
        public SinglyLinkedListNode tail;

        public SinglyLinkedList() {
            this.head = null;
            this.tail = null;
        }

        public void insertNode(int nodeData) {
            SinglyLinkedListNode node = new SinglyLinkedListNode(nodeData);

            if (this.head == null) {
                this.head = node;
            } else {
                this.tail.next = node;
            }

            this.tail = node;
        }
    }

    static void printLinkedList(SinglyLinkedListNode head) {
        SinglyLinkedListNode temp = head;
        while (temp != null) {
            System.out.print(temp.value + " ");
            temp = temp.next;
        }
        System.out.println();
    }

static SinglyLinkedListNode ArrangeSalary(SinglyLinkedListNode head, int X) {

    /* if list has 0 or 1 elements then return */
    if(head == null || head.next == null)
      return head;

    /* create two lists one for storing smaller elements than X and
      another for storing greater than or equal to elements than X */

    /* head pointer for smaller list */
    SinglyLinkedListNode smaller = null;

    /*pointer to the last element in the smaller list */
    SinglyLinkedListNode temp_smaller = null;

     /* head pointer for greater list */
    SinglyLinkedListNode greater = null;

    /*pointer to the last element in the greater list */
    SinglyLinkedListNode temp_greater = null;

    SinglyLinkedListNode temp = head;

    while(temp != null){
      SinglyLinkedListNode t = temp;
      temp = temp.next;

      if(t.value < X){
        if(smaller == null){
          smaller = t;
          temp_smaller = t;
          t.next = null;
        }
        else{
          temp_smaller.next = t;
          t.next = null;
          temp_smaller = t;
        }

      }
      else{
        if(greater == null){
          greater = t;
          temp_greater = t;
          t.next = null;
        }
        else{
          temp_greater.next = t;
          t.next = null;
          temp_greater = t;
        }
      }
    }

    /* concatenating both smaller and greater lists */
    temp_smaller.next = greater;

      return smaller;
}


    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {

        SinglyLinkedList llist = new SinglyLinkedList();
        int size = scanner.nextInt();
        int X = scanner.nextInt();

        for (int i = 0; i < size; i++) {
            int llistItem = scanner.nextInt();

            llist.insertNode(llistItem);
        }
        SinglyLinkedListNode temp = ArrangeSalary(llist.head, X);
        printLinkedList(temp);

    }
}

Space Complexity: O(1)

[forminator_quiz id="2131"]

This article tried to discuss the concept of Basic Pointer Manipulation. Hope this blog helps you understand the concept of Basic Pointer Manipulatio. To practice more problems you can check out MYCODE|COMPETITIVE PROGRAMMING

Leave a Reply

Your email address will not be published. Required fields are marked *

Close

Related Post