Вставить N элементов в связанный список один за другим в средней позиции

Опубликовано: 14 Января, 2022

Дан массив из N элементов. Задача состоит в том, чтобы вставить указанные элементы в середину связного списка один за другим. Каждая операция вставки должна занимать O (1) временную сложность.

Примеры:

Input: arr[] = {1, 2, 3, 4, 5}
Output: 1 -> 3 -> 5 -> 4 -> 2 -> NULL
1 -> NULL
1 -> 2 -> NULL
1 -> 3 -> 2 -> NULL
1 -> 3 -> 4 -> 2 -> NULL
1 -> 3 -> 5 -> 4 -> 2 -> NULL

Input: arr[] = {5, 4, 1, 2}
Output: 5 -> 1 -> 2 -> 4 -> NULL

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: Возможны два случая:

  1. Количество элементов в списке меньше 2.
  2. Количество элементов в списке больше 2.
    • Количество уже присутствующих элементов равно N, тогда новый элемент вставляется в среднюю позицию, равную (N / 2) + 1 .
    • Количество уже присутствующих элементов нечетное, тогда новый элемент вставляется рядом с текущим средним элементом, который равен (N / 2) + 2 .

Мы берем один дополнительный указатель «средний», в котором хранится адрес текущего среднего элемента, и счетчик, который считает общее количество элементов.
Если элементов, уже присутствующих в связанном списке, меньше 2, то середина всегда будет указывать на первую позицию, и мы вставляем новый узел после текущей середины.
Если элементов, уже присутствующих в связанном списке, больше двух, мы вставляем новый узел рядом с текущей серединой и увеличиваем счетчик.
Если после вставки осталось нечетное количество элементов, то середина указывает на вновь вставленный узел, иначе средний указатель не изменится.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <iostream>
using namespace std;
  
// Node structure
struct Node {
  
    int value;
    struct Node* next;
};
  
// Class to represent a node
// of the linked list
class LinkedList {
  
private:
    struct Node *head, *mid;
    int count;
  
public:
    LinkedList();
    void insertAtMiddle(int);
    void show();
};
  
LinkedList::LinkedList()
{
    head = NULL;
    mid = NULL;
    count = 0;
}
  
// Function to insert a node in
// the middle of the linked list
void LinkedList::insertAtMiddle(int n)
{
  
    struct Node* temp = new struct Node();
    struct Node* temp1;
  
    temp->next = NULL;
    temp->value = n;
  
    // If the number of elements
    // already present are less than 2
    if (count < 2) {
        if (head == NULL) {
            head = temp;
        }
        else {
            temp1 = head;
            temp1->next = temp;
        }
        count++;
  
        // mid points to first element
        mid = head;
    }
  
    // If the number of elements already present
    // are greater than 2
    else {
  
        temp->next = mid->next;
        mid->next = temp;
        count++;
  
        // If number of elements after insertion
        // are odd
        if (count % 2 != 0) {
  
            // mid points to the newly
            // inserted node
            mid = mid->next;
        }
    }
}
  
// Function to print the nodes
// of the linked list
void LinkedList::show()
{
  
    struct Node* temp;
  
    temp = head;
  
    // Initializing temp to head
    // Iterating and printing till
    // The end of linked list
    // That is, till temp is null
    while (temp != NULL) {
  
        cout << temp->value << " -> ";
        temp = temp->next;
    }
    cout << "NULL";
    cout << endl;
}
  
// Driver code
int main()
{
    // Elements to be inserted one after another
    int arr[] = { 1, 2, 3, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
  
    LinkedList L1;
  
    // Insert the elements
    for (int i = 0; i < n; i++)
        L1.insertAtMiddle(arr[i]);
  
    // Print the nodes of the linked list
    L1.show();
  
    return 0;
}

Java

// Java implementation of the approach 
class GFG
{
  
// Node ure 
static class Node 
{ 
  
    int value; 
    Node next; 
}; 
  
// Class to represent a node 
// of the linked list 
static class LinkedList 
{ 
    Node head, mid; 
    int count; 
  
  
LinkedList() 
{ 
    head = null; 
    mid = null; 
    count = 0; 
} 
  
// Function to insert a node in 
// the middle of the linked list 
void insertAtMiddle(int n) 
{ 
  
    Node temp = new Node(); 
    Node temp1; 
  
    temp.next = null; 
    temp.value = n; 
  
    // If the number of elements 
    // already present are less than 2 
    if (count < 2) 
    { 
        if (head == null) 
        { 
            head = temp; 
        } 
        else 
        { 
            temp1 = head; 
            temp1.next = temp; 
        } 
        count++; 
  
        // mid points to first element 
        mid = head; 
    } 
  
    // If the number of elements already present 
    // are greater than 2 
    else 
    { 
  
        temp.next = mid.next; 
        mid.next = temp; 
        count++; 
  
        // If number of elements after insertion 
        // are odd 
        if (count % 2 != 0) 
        { 
  
            // mid points to the newly 
            // inserted node 
            mid = mid.next; 
        } 
    } 
} 
  
// Function to print the nodes 
// of the linked list 
void show() 
{ 
  
    Node temp; 
  
    temp = head; 
  
    // Initializing temp to head 
    // Iterating and printing till 
    // The end of linked list 
    // That is, till temp is null 
    while (temp != null) 
    { 
  
        System.out.print( temp.value + " -> "); 
        temp = temp.next; 
    } 
    System.out.print( "null"); 
    System.out.println();
} 
  
}
  
// Driver code 
public static void main(String args[])
{ 
    // Elements to be inserted one after another 
    int arr[] = { 1, 2, 3, 4, 5 }; 
    int n = arr.length; 
  
    LinkedList L1=new LinkedList(); 
  
    // Insert the elements 
    for (int i = 0; i < n; i++) 
        L1.insertAtMiddle(arr[i]); 
  
    // Print the nodes of the linked list 
    L1.show(); 
}
}
  
// This code is contributed by Arnab Kundu

Python3

# Python3 implementation of the approach 
  
# Node ure 
class Node: 
    def __init__(self):
        self.value = 0
        self.next = None
  
# Class to represent a node 
# of the linked list 
class LinkedList: 
  
    def __init__(self) :
        self.head = None
        self.mid = None
        self.count = 0
  
    # Function to insert a node in 
    # the middle of the linked list 
    def insertAtMiddle(self , n): 
  
        temp = Node() 
        temp1 = None
  
        temp.next = None
        temp.value = n 
  
        # If the number of elements 
        # already present are less than 2 
        if (self.count < 2): 
      
            if (self.head == None) :
          
                self.head = temp 
          
            else:
          
                temp1 = self.head 
                temp1.next = temp 
          
            self.count = self.count + 1
  
            # mid points to first element 
            self.mid = self.head 
      
        # If the number of elements already present 
        # are greater than 2 
        else:
      
            temp.next = self.mid.next
            self.mid.next = temp 
            self.count = self.count + 1
  
            # If number of elements after insertion 
            # are odd 
            if (self.count % 2 != 0): 
          
                # mid points to the newly 
                # inserted node 
                self.mid = self.mid.next
          
    # Function to print the nodes 
    # of the linked list 
    def show(self): 
        temp = None
  
        temp = self.head 
  
        # Initializing temp to self.head 
        # Iterating and printing till 
        # The end of linked list 
        # That is, till temp is None 
        while (temp != None) :
      
            print( temp.value, end = " -> ") 
            temp = temp.next
      
        print( "None") 
  
# Driver code 
  
# Elements to be inserted one after another 
arr = [ 1, 2, 3, 4, 5] 
n = len(arr) 
  
L1 = LinkedList() 
  
# Insert the elements 
for i in range(n): 
    L1.insertAtMiddle(arr[i]) 
  
# Print the nodes of the linked list 
L1.show() 
  
# This code is contributed by Arnab Kundu

C#

// C# implementation of the approach 
using System;
  
class GFG
{
  
// Node ure 
public class Node 
{ 
  
    public int value; 
    public Node next; 
}; 
  
// Class to represent a node 
// of the linked list 
public class LinkedList 
{ 
    public Node head, mid; 
    public int count; 
  
  
public LinkedList() 
{ 
    head = null; 
    mid = null; 
    count = 0; 
} 
  
// Function to insert a node in 
// the middle of the linked list 
public void insertAtMiddle(int n) 
{ 
  
    Node temp = new Node(); 
    Node temp1; 
  
    temp.next = null; 
    temp.value = n; 
  
    // If the number of elements 
    // already present are less than 2 
    if (count < 2) 
    { 
        if (head == null) 
        { 
            head = temp; 
        } 
        else
        { 
            temp1 = head; 
            temp1.next = temp; 
        } 
        count++; 
  
        // mid points to first element 
        mid = head; 
    } 
  
    // If the number of elements already present 
    // are greater than 2 
    else

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Подсчитайте числа Фибоначчи в заданном диапазоне за время O (Log n) и пространство O (1)
21 Января, 2022
Сгенерировать все перестановки набора в Python
21 Января, 2022
Найдите максимальное расстояние, которое можно преодолеть на n велосипедах
21 Января, 2022
Алгоритм МО (разложение квадратного корня запроса) | Набор 1 (Введение)
21 Января, 2022
Подсчитайте количество способов разделить число на 4 части
21 Января, 2022
Проверьте, можно ли сделать все биты одинаковыми с помощью одного переворота
20 Января, 2022
Алгоритм генерации линий Брезенхема
20 Января, 2022
Максимальная площадь треугольника с разными цветами вершин
20 Января, 2022