Excluir meio da lista vinculada
Dada uma lista individual vinculada, a tarefa é excluir o nó do meio da lista.
- Se a lista contiver um número par de nós, haverá dois nós do meio. Nesse caso, exclua o segundo nó do meio.
- Se a lista vinculada consistir em apenas um nó, retorne nulo.
Exemplo:
Entrada: LinkedList: 1-> 2-> 3-> 4-> 5
Saída: 1-> 2-> 4-> 5
Explicação:
Entrada: LinkedList: 2-> 4-> 6-> 7-> 5-> 1
Saída: 2-> 4-> 6-> 5-> 1
Explicação:
Entrada: LinkedList: 7
Saída:
Tabela de conteúdo
- [Abordagem ingênua] usando travessia de dois passos - o (n) tempo e o (1) espaço
- [Abordagem esperada] Travessal de uma passagem com ponteiros lentos e rápidos - o (n) tempo e o (1) espaço
[Abordagem ingênua] usando travessia de dois passos - o (n) tempo e o (1) espaço
A idéia básica por trás dessa abordagem é primeiro atravessar toda a lista vinculada para contar o número total de nós. Depois que conhecemos o número total de nós, podemos calcular a posição do nó do meio, que está no índice n/2 (onde n é o número total de nós). Em seguida, passe pela lista vinculada novamente, mas desta vez paramos antes do nó do meio. Uma vez lá, modificamos o próximo ponteiro do nó antes do nó do meio, para que ele pula o nó do meio e aponte diretamente para o nó depois dele
Abaixo está a implementação da abordagem acima:
C++ // C++ program to delete middle of a linked list #include using namespace std ; struct Node { int data ; Node * next ; Node ( int x ){ data = x ; next = nullptr ; } }; // Function to delete middle node from linked list. Node * deleteMid ( Node * head ) { // Edge case: return nullptr if there is only // one node. if ( head -> next == nullptr ) return nullptr ; int count = 0 ; Node * p1 = head * p2 = head ; // First pass count the number of nodes // in the linked list using 'p1'. while ( p1 != nullptr ) { count ++ ; p1 = p1 -> next ; } // Get the index of the node to be deleted. int middleIndex = count / 2 ; // Second pass let 'p2' move toward the predecessor // of the middle node. for ( int i = 0 ; i < middleIndex - 1 ; ++ i ) p2 = p2 -> next ; // Delete the middle node and return 'head'. p2 -> next = p2 -> next -> next ; return head ; } void printList ( Node * head ) { Node * temp = head ; while ( temp != nullptr ) { cout < < temp -> data < < ' -> ' ; temp = temp -> next ; } cout < < 'nullptr' < < endl ; } int main () { // Create a static hardcoded linked list: // 1 -> 2 -> 3 -> 4 -> 5. Node * head = new Node ( 1 ); head -> next = new Node ( 2 ); head -> next -> next = new Node ( 3 ); head -> next -> next -> next = new Node ( 4 ); head -> next -> next -> next -> next = new Node ( 5 ); cout < < 'Original Linked List: ' ; printList ( head ); // Delete the middle node. head = deleteMid ( head ); cout < < 'Linked List after deleting the middle node: ' ; printList ( head ); return 0 ; }
C // C program to delete middle of a linked list #include #include struct Node { int data ; struct Node * next ; }; // Function to delete middle node from linked list. struct Node * deleteMid ( struct Node * head ) { // Edge case: return NULL if there is only // one node. if ( head -> next == NULL ) return NULL ; int count = 0 ; struct Node * p1 = head * p2 = head ; // First pass count the number of nodes // in the linked list using 'p1'. while ( p1 != NULL ) { count ++ ; p1 = p1 -> next ; } // Get the index of the node to be deleted. int middleIndex = count / 2 ; // Second pass let 'p2' move toward the predecessor // of the middle node. for ( int i = 0 ; i < middleIndex - 1 ; ++ i ) p2 = p2 -> next ; // Delete the middle node and return 'head'. p2 -> next = p2 -> next -> next ; return head ; } void printList ( struct Node * head ) { struct Node * temp = head ; while ( temp != NULL ) { printf ( '%d -> ' temp -> data ); temp = temp -> next ; } printf ( 'NULL n ' ); } struct Node * newNode ( int x ) { struct Node * temp = ( struct Node * ) malloc ( sizeof ( struct Node )); temp -> data = x ; temp -> next = NULL ; return temp ; } int main () { // Create a static hardcoded linked list: // 1 -> 2 -> 3 -> 4 -> 5. struct Node * head = newNode ( 1 ); head -> next = newNode ( 2 ); head -> next -> next = newNode ( 3 ); head -> next -> next -> next = newNode ( 4 ); head -> next -> next -> next -> next = newNode ( 5 ); printf ( 'Original Linked List: ' ); printList ( head ); // Delete the middle node. head = deleteMid ( head ); printf ( 'Linked List after deleting the middle node: ' ); printList ( head ); return 0 ; }
Java // Java program to delete middle of a linked list class Node { int data ; Node next ; Node ( int x ) { data = x ; next = null ; } } public class GfG { // Function to delete middle node from linked list. public static Node deleteMid ( Node head ) { // Edge case: return null if there is only // one node. if ( head . next == null ) return null ; int count = 0 ; Node p1 = head p2 = head ; // First pass count the number of nodes // in the linked list using 'p1'. while ( p1 != null ) { count ++ ; p1 = p1 . next ; } // Get the index of the node to be deleted. int middleIndex = count / 2 ; // Second pass let 'p2' move toward predecessor // of the middle node. for ( int i = 0 ; i < middleIndex - 1 ; ++ i ) p2 = p2 . next ; // Delete the middle node and return 'head'. p2 . next = p2 . next . next ; return head ; } public static void printList ( Node head ) { Node temp = head ; while ( temp != null ) { System . out . print ( temp . data + ' -> ' ); temp = temp . next ; } System . out . println ( 'null' ); } public static void main ( String [] args ) { // Create a static hardcoded linked list: // 1 -> 2 -> 3 -> 4 -> 5. Node head = new Node ( 1 ); head . next = new Node ( 2 ); head . next . next = new Node ( 3 ); head . next . next . next = new Node ( 4 ); head . next . next . next . next = new Node ( 5 ); System . out . print ( 'Original Linked List: ' ); printList ( head ); // Delete the middle node. head = deleteMid ( head ); System . out . print ( 'Linked List after deleting the middle node: ' ); printList ( head ); } }
Python # Python3 program to delete middle of a linked list class Node : def __init__ ( self data ): self . data = data self . next = None # Function to delete middle node from linked list. def deleteMid ( head ): # Edge case: return None if there is only # one node. if head . next is None : return None count = 0 p1 = head p2 = head # First pass count the number of nodes # in the linked list using 'p1'. while p1 is not None : count += 1 p1 = p1 . next # Get the index of the node to be deleted. middleIndex = count // 2 # Second pass let 'p2' move toward the predecessor # of the middle node. for i in range ( middleIndex - 1 ): p2 = p2 . next # Delete the middle node and return 'head'. p2 . next = p2 . next . next return head def printList ( head ): temp = head while temp is not None : print ( temp . data end = ' -> ' ) temp = temp . next print ( 'None' ) if __name__ == '__main__' : # Create a static hardcoded linked list: # 1 -> 2 -> 3 -> 4 -> 5. head = Node ( 1 ) head . next = Node ( 2 ) head . next . next = Node ( 3 ) head . next . next . next = Node ( 4 ) head . next . next . next . next = Node ( 5 ) print ( 'Original Linked List:' end = ' ' ) printList ( head ) # Delete the middle node. head = deleteMid ( head ) print ( 'Linked List after deleting the middle node:' end = ' ' ) printList ( head )
C# // C# program to delete middle of a linked list using System ; class Node { public int data ; public Node next ; public Node ( int x ) { data = x ; next = null ; } } class GfG { // Function to delete middle node from linked list. static Node deleteMid ( Node head ) { // Edge case: return null if there is only // one node. if ( head . next == null ) return null ; int count = 0 ; Node p1 = head p2 = head ; // First pass count the number of nodes // in the linked list using 'p1'. while ( p1 != null ) { count ++ ; p1 = p1 . next ; } // Get the index of the node to be deleted. int middleIndex = count / 2 ; // Second pass let 'p2' move toward the predecessor // of the middle node. for ( int i = 0 ; i < middleIndex - 1 ; ++ i ) p2 = p2 . next ; // Delete the middle node and return 'head'. p2 . next = p2 . next . next ; return head ; } static void printList ( Node head ) { Node temp = head ; while ( temp != null ) { Console . Write ( temp . data + ' -> ' ); temp = temp . next ; } Console . WriteLine ( 'null' ); } static void Main ( string [] args ) { // Create a static hardcoded linked list: // 1 -> 2 -> 3 -> 4 -> 5. Node head = new Node ( 1 ); head . next = new Node ( 2 ); head . next . next = new Node ( 3 ); head . next . next . next = new Node ( 4 ); head . next . next . next . next = new Node ( 5 ); Console . Write ( 'Original Linked List: ' ); printList ( head ); // Delete the middle node. head = deleteMid ( head ); Console . Write ( 'Linked List after deleting the middle node: ' ); printList ( head ); } }
JavaScript class Node { constructor ( data ) { this . data = data ; this . next = null ; } } // Function to delete middle node from linked list. function deleteMid ( head ) { // Edge case: return null if there is only // one node. if ( head . next === null ) return null ; let count = 0 ; let p1 = head p2 = head ; // First pass count the number of nodes // in the linked list using 'p1'. while ( p1 !== null ) { count ++ ; p1 = p1 . next ; } // Get the index of the node to be deleted. let middleIndex = Math . floor ( count / 2 ); // Second pass let 'p2' move toward the predecessor // of the middle node. for ( let i = 0 ; i < middleIndex - 1 ; ++ i ) p2 = p2 . next ; // Delete the middle node and return 'head'. p2 . next = p2 . next . next ; return head ; } function printList ( head ) { let temp = head ; while ( temp !== null ) { console . log ( temp . data + ' -> ' ); temp = temp . next ; } console . log ( 'null' ); } // Create a static hardcoded linked list: // 1 -> 2 -> 3 -> 4 -> 5. let head = new Node ( 1 ); head . next = new Node ( 2 ); head . next . next = new Node ( 3 ); head . next . next . next = new Node ( 4 ); head . next . next . next . next = new Node ( 5 ); console . log ( 'Original Linked List: ' ); printList ( head ); // Delete the middle node. head = deleteMid ( head ); console . log ( 'Linked List after deleting the middle node: ' ); printList ( head );
Saída
Original Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> nullptr Linked List after deleting the middle node: 1 -> 2 -> 4 -> 5 -> nullptr
Complexidade do tempo: Sobre). São necessários dois travessia da lista vinculada
Espaço auxiliar: O (1). Nenhum espaço extra é necessário.
[Abordagem esperada] Travessal de uma passagem com ponteiros lentos e rápidos - o (n) tempo e o (1) espaço
A solução acima requer dois travessos da lista vinculada. O nó do meio pode ser excluído usando uma travessia. A idéia é usar dois ponteiros Slow_Ptr e fast_ptr . O ponteiro rápido move dois nós de cada vez, enquanto o ponteiro lento se move um nó de cada vez. Quando o ponteiro rápido chegar ao final da lista, o ponteiro lento será posicionado no nó do meio. Em seguida, você precisa conectar o nó que vem antes do nó do meio ( Anterior ) para o nó que vem após o nó do meio. Isso pula efetivamente sobre o nó do meio, removendo -o da lista.
Abaixo está a implementação da abordagem acima
C++ // C++ program to delete middle of a linked list #include using namespace std ; struct Node { int data ; Node * next ; Node ( int x ){ data = x ; next = nullptr ; } }; // Function to delete middle node from linked list struct Node * deleteMid ( struct Node * head ) { // If the list is empty return NULL if ( head == NULL ) return NULL ; // If the list has only one node // delete it and return NULL if ( head -> next == NULL ) { delete head ; return NULL ; } struct Node * prev = NULL ; struct Node * slow_ptr = head ; struct Node * fast_ptr = head ; // Move the fast pointer 2 nodes ahead // and the slow pointer 1 node ahead // until fast pointer reaches end of the list while ( fast_ptr != NULL && fast_ptr -> next != NULL ) { fast_ptr = fast_ptr -> next -> next ; // Update prev to hold the previous // slow pointer value prev = slow_ptr ; slow_ptr = slow_ptr -> next ; } // At this point slow_ptr points to middle node // Bypass the middle node prev -> next = slow_ptr -> next ; // Delete the middle node delete slow_ptr ; // Return the head of the modified list return head ; } void printList ( struct Node * head ) { struct Node * temp = head ; while ( temp != NULL ) { cout < < temp -> data < < ' -> ' ; temp = temp -> next ; } cout < < 'NULL' < < endl ; } int main () { // Create a static hardcoded linked list: // 1 -> 2 -> 3 -> 4 -> 5 Node * head = new Node ( 1 ); head -> next = new Node ( 2 ); head -> next -> next = new Node ( 3 ); head -> next -> next -> next = new Node ( 4 ); head -> next -> next -> next -> next = new Node ( 5 ); cout < < 'Original Linked List: ' ; printList ( head ); // Delete the middle node head = deleteMid ( head ); cout < < 'Linked List after deleting the middle node: ' ; printList ( head ); return 0 ; }
C // C program to delete middle of a linked list #include #include struct Node { int data ; struct Node * next ; }; // Function to delete middle node from linked list struct Node * deleteMid ( struct Node * head ) { // If the list is empty return NULL if ( head == NULL ) return NULL ; // If the list has only one node // delete it and return NULL if ( head -> next == NULL ) { free ( head ); return NULL ; } struct Node * prev = NULL ; struct Node * slow_ptr = head ; struct Node * fast_ptr = head ; // Move the fast pointer 2 nodes ahead // and the slow pointer 1 node ahead // until fast pointer reaches end of the list while ( fast_ptr != NULL && fast_ptr -> next != NULL ) { fast_ptr = fast_ptr -> next -> next ; // Update prev to hold the previous // slow pointer value prev = slow_ptr ; slow_ptr = slow_ptr -> next ; } // At this point slow_ptr points to middle node // Bypass the middle node prev -> next = slow_ptr -> next ; // Delete the middle node free ( slow_ptr ); // Return the head of the modified list return head ; } void printList ( struct Node * head ) { struct Node * temp = head ; while ( temp != NULL ) { printf ( '%d -> ' temp -> data ); temp = temp -> next ; } printf ( 'NULL n ' ); } struct Node * newNode ( int x ) { struct Node * temp = ( struct Node * ) malloc ( sizeof ( struct Node )); temp -> data = x ; temp -> next = NULL ; return temp ; } int main () { // Create a static hardcoded linked list: // 1 -> 2 -> 3 -> 4 -> 5. struct Node * head = newNode ( 1 ); head -> next = newNode ( 2 ); head -> next -> next = newNode ( 3 ); head -> next -> next -> next = newNode ( 4 ); head -> next -> next -> next -> next = newNode ( 5 ); printf ( 'Original Linked List: ' ); printList ( head ); // Delete the middle node. head = deleteMid ( head ); printf ( 'Linked List after deleting the middle node: ' ); printList ( head ); return 0 ; }
Java // Java program to delete the middle of a linked list class Node { int data ; Node next ; Node ( int x ) { data = x ; next = null ; } } class GfG { // Function to delete middle node from linked list static Node deleteMid ( Node head ) { // If the list is empty return null if ( head == null ) return null ; // If the list has only one node // delete it and return null if ( head . next == null ) { return null ; } Node prev = null ; Node slow_ptr = head ; Node fast_ptr = head ; // Move the fast pointer 2 nodes ahead // and the slow pointer 1 node ahead // until fast pointer reaches end of list while ( fast_ptr != null && fast_ptr . next != null ) { fast_ptr = fast_ptr . next . next ; // Update prev to hold the previous // slow pointer value prev = slow_ptr ; slow_ptr = slow_ptr . next ; } // At this pointslow_ptr points to middle node // Bypass the middle node prev . next = slow_ptr . next ; // Return the head of the modified list return head ; } static void printList ( Node head ) { Node temp = head ; while ( temp != null ) { System . out . print ( temp . data + ' -> ' ); temp = temp . next ; } System . out . println ( 'NULL' ); } public static void main ( String [] args ) { // Create a static hardcoded linked list: // 1 -> 2 -> 3 -> 4 -> 5 Node head = new Node ( 1 ); head . next = new Node ( 2 ); head . next . next = new Node ( 3 ); head . next . next . next = new Node ( 4 ); head . next . next . next . next = new Node ( 5 ); System . out . print ( 'Original Linked List: ' ); printList ( head ); // Delete the middle node head = deleteMid ( head ); System . out . print ( 'Linked List after deleting the middle node: ' ); printList ( head ); } }
Python # Python program to delete the middle of a linked list class Node : def __init__ ( self data ): self . data = data self . next = None # Function to delete middle node from linked list def deleteMid ( head ): # If the list is empty return None if head is None : return None # If the list has only one node # delete it and return None if head . next is None : return None prev = None slow_ptr = head fast_ptr = head # Move the fast pointer 2 nodes ahead # and the slow pointer 1 node ahead # until fast pointer reaches end of the list while fast_ptr is not None and fast_ptr . next is not None : fast_ptr = fast_ptr . next . next # Update prev to hold the previous # slow pointer value prev = slow_ptr slow_ptr = slow_ptr . next # At this point slow_ptr points to middle node # Bypass the middle node prev . next = slow_ptr . next # Return the head of the modified list return head def printList ( head ): temp = head while temp : print ( temp . data end = ' -> ' ) temp = temp . next print ( 'NULL' ) if __name__ == '__main__' : # Create a static hardcoded linked list: # 1 -> 2 -> 3 -> 4 -> 5 head = Node ( 1 ) head . next = Node ( 2 ) head . next . next = Node ( 3 ) head . next . next . next = Node ( 4 ) head . next . next . next . next = Node ( 5 ) print ( 'Original Linked List: ' end = '' ) printList ( head ) # Delete the middle node head = deleteMid ( head ) print ( 'Linked List after deleting the middle node: ' end = '' ) printList ( head )
C# // C# program to delete middle of a linked list using System ; class Node { public int data ; public Node next ; public Node ( int x ) { data = x ; next = null ; } } class GfG { // Function to delete middle node from linked list public static Node deleteMid ( Node head ) { // If the list is empty return null if ( head == null ) return null ; // If the list has only one node // delete it and return null if ( head . next == null ) { return null ; } Node prev = null ; Node slow_ptr = head ; Node fast_ptr = head ; // Move the fast pointer 2 nodes ahead // and the slow pointer 1 node ahead // until fast pointer reaches end of the list while ( fast_ptr != null && fast_ptr . next != null ) { fast_ptr = fast_ptr . next . next ; // Update prev to hold the previous // slow pointer value prev = slow_ptr ; slow_ptr = slow_ptr . next ; } // At this point slow_ptr points to middle node // Bypass the middle node prev . next = slow_ptr . next ; // Return the head of the modified list return head ; } // Function to print the linked list public static void printList ( Node head ) { Node temp = head ; while ( temp != null ) { Console . Write ( temp . data + ' -> ' ); temp = temp . next ; } Console . WriteLine ( 'NULL' ); } public static void Main ( string [] args ) { // Create a static hardcoded linked list: // 1 -> 2 -> 3 -> 4 -> 5 Node head = new Node ( 1 ); head . next = new Node ( 2 ); head . next . next = new Node ( 3 ); head . next . next . next = new Node ( 4 ); head . next . next . next . next = new Node ( 5 ); Console . Write ( 'Original Linked List: ' ); printList ( head ); // Delete the middle node head = deleteMid ( head ); Console . Write ( 'Linked List after deleting the middle node: ' ); printList ( head ); } }
JavaScript // javascript program to delete middle of a linked list class Node { constructor ( data ) { this . data = data ; this . next = null ; } } // Function to delete the middle node from the linked list function deleteMid ( head ) { // If the list is empty return null if ( head === null ) { return null ; } // If the list has only one node delete it and return // null if ( head . next === null ) { return null ; } let prev = null ; let slow_ptr = head ; let fast_ptr = head ; // Move the fast pointer 2 nodes ahead // and the slow pointer 1 node ahead // until the fast pointer reaches the end of the list while ( fast_ptr !== null && fast_ptr . next !== null ) { fast_ptr = fast_ptr . next . next ; // Update prev to hold the previous slow pointer // value prev = slow_ptr ; slow_ptr = slow_ptr . next ; } // At this point slow_ptr points to the middle node // Bypass the middle node prev . next = slow_ptr . next ; // Return the head of the modified list return head ; } function printList ( head ) { let temp = head ; while ( temp !== null ) { process . stdout . write ( temp . data + ' -> ' ); temp = temp . next ; } console . log ( 'null' ); } // Create a static hardcoded linked list: // 1 -> 2 -> 3 -> 4 -> 5 let head = new Node ( 1 ); head . next = new Node ( 2 ); head . next . next = new Node ( 3 ); head . next . next . next = new Node ( 4 ); head . next . next . next . next = new Node ( 5 ); process . stdout . write ( 'Original Linked List: ' ); printList ( head ); // Delete the middle node head = deleteMid ( head ); process . stdout . write ( 'Linked List after deleting the middle node: ' ); printList ( head );
Saída
Original Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> NULL Linked List after deleting the middle node: 1 -> 2 -> 4 -> 5 -> NULL
Complexidade do tempo: Sobre). Apenas uma travessia da lista vinculada é necessária
Espaço auxiliar: O (1). Como não é necessário espaço extra.
Artigo relacionado:
- Encontre o meio da lista vinculada
