Вставить N элементов в связанный список один за другим в средней позиции
Дан массив из 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 -> NULLInput: arr[] = {5, 4, 1, 2}
Output: 5 -> 1 -> 2 -> 4 -> NULL
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Подход: Возможны два случая:
- Количество элементов в списке меньше 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
РЕКОМЕНДУЕМЫЕ СТАТЬИ |