Dada una lista doblemente enlazada que tiene todos los elementos únicos y dos claves X e Y , la tarea es intercambiar Nodes por dos claves dadas cambiando solo los enlaces.
Nota: Se puede considerar que X e Y siempre están presentes en la lista.
Ejemplos :
Entrada : lista = 1 <-> 8 <-> 7 <-> 9 <-> 4, X = 1, Y = 4
Salida : 4 <-> 8 <-> 7 <-> 9 <-> 1Entrada : lista = 0 <-> 1, X = 0, Y = 1
Salida : 1 <-> 0
Enfoque : el problema se puede resolver cruzando punteros a Nodes que tengan valores X e Y e intercambiándolos .
Siga los pasos que se mencionan a continuación:
- Busque X e Y en la lista doblemente enlazada dada.
- Después de buscar, intercambie los Nodes haciendo que el anterior puntero adyacente de X sea el anterior puntero adyacente de Y y el siguiente puntero adyacente de X sea el siguiente puntero adyacente de Y y viceversa.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach #include <bits/stdc++.h> using namespace std; // Link list Node Class class Node { public: int data; Node* prev; Node* next; // Constructor function Node(int data) { this->data = data; this->prev = NULL; this->next = NULL; } }; // Function to print linked list void print(Node* head) { Node* temp = head; // Iterate until node is NOT NULL while (temp != NULL) { cout << temp->data << " "; temp = temp->next; } cout << endl; } // Function to push a node in DLL void push(Node*& head, Node*& tail, int item) { // DLL is empty if (tail == NULL) { Node* temp = new Node(item); tail = temp; head = temp; } // DLL is not empty else { Node* temp = new Node(item); tail->next = temp; temp->prev = tail; tail = temp; } } // Function to find the nodes // which have to be swapped pair<Node*, Node*> find(Node*& head, int x, int y) { Node* N1 = NULL; Node* N2 = NULL; Node* temp = head; // Traversing the list while (temp != NULL) { if (temp->data == x) N1 = temp; else if (temp->data == y) N2 = temp; temp = temp->next; } return make_pair(N1, N2); } // Function to swap the nodes // consisting of x and y void swap(Node*& head, Node*& tail, int x, int y) { // Edge Cases if (head == NULL || head->next == NULL || x == y) return; // Finding the Nodes pair<Node*, Node*> p = find(head, x, y); Node* Node1 = p.first; Node* Node2 = p.second; if (Node1 == head) head = Node2; else if (Node2 == head) head = Node1; if (Node1 == tail) tail = Node2; else if (Node2 == tail) tail = Node1; // Swapping Node1 and Node2 Node* temp; temp = Node1->next; Node1->next = Node2->next; Node2->next = temp; if (Node1->next != NULL) Node1->next->prev = Node1; if (Node2->next != NULL) Node2->next->prev = Node2; temp = Node1->prev; Node1->prev = Node2->prev; Node2->prev = temp; if (Node1->prev != NULL) Node1->prev->next = Node1; if (Node2->prev != NULL) Node2->prev->next = Node2; } // Driver Code int main() { Node* head = NULL; Node* tail = NULL; push(head, tail, 1); push(head, tail, 8); push(head, tail, 7); push(head, tail, 9); push(head, tail, 4); int X = 1, Y = 4; cout << "Before Swapping: "; print(head); swap(head, tail, X, Y); cout << "After Swapping: "; print(head); return 0; }
Java
// Java code to implement the above approach import java.util.*; class GFG{ // Link list Node Class static class Node { int data; Node prev; Node next; // Constructor function Node(int data) { this.data = data; this.prev = null; this.next = null; } }; static class pair { Node first, second; public pair(Node first, Node second) { this.first = first; this.second = second; } } // Function to print linked list static void print(Node head) { Node temp = head; // Iterate until node is NOT null while (temp != null) { System.out.print(temp.data+ " "); temp = temp.next; } System.out.println(); } static Node head; static Node tail; // Function to push a node in DLL static void push( int item) { // DLL is empty if (tail == null) { Node temp = new Node(item); tail = temp; head = temp; } // DLL is not empty else { Node temp = new Node(item); tail.next = temp; temp.prev = tail; tail = temp; } } // Function to find the nodes // which have to be swapped static pair find(int x, int y) { Node N1 = null; Node N2 = null; Node temp = head; // Traversing the list while (temp != null) { if (temp.data == x) N1 = temp; else if (temp.data == y) N2 = temp; temp = temp.next; } return new pair(N1, N2); } // Function to swap the nodes // consisting of x and y static void swap( int x, int y) { // Edge Cases if (head == null || head.next == null || x == y) return; // Finding the Nodes pair p = find( x, y); Node Node1 = p.first; Node Node2 = p.second; if (Node1 == head) head = Node2; else if (Node2 == head) head = Node1; if (Node1 == tail) tail = Node2; else if (Node2 == tail) tail = Node1; // Swapping Node1 and Node2 Node temp; temp = Node1.next; Node1.next = Node2.next; Node2.next = temp; if (Node1.next != null) Node1.next.prev = Node1; if (Node2.next != null) Node2.next.prev = Node2; temp = Node1.prev; Node1.prev = Node2.prev; Node2.prev = temp; if (Node1.prev != null) Node1.prev.next = Node1; if (Node2.prev != null) Node2.prev.next = Node2; } // Driver Code public static void main(String[] args) { head = null; tail = null; push( 1); push( 8); push(7); push(9); push( 4); int X = 1, Y = 4; System.out.print("Before Swapping: "); print(head); swap( X, Y); System.out.print("After Swapping: "); print(head); } } // This code is contributed by shikhasingrajput
Python3
# Python code to implement the above approach # Link list Node Class class Node: def __init__(self, data): self.data = data self.prev = None self.next = None class pair: def __init__(self, first, second): self.first = first self.second = second class DoublyLL: def __init__(self): self.head = None self.tail = None # Function to print linked list def print_list(self): temp = self.head while temp: print(temp.data, end=" ") temp = temp.next print() # Function to push a node in DLL def push(self, item): # DLL is empty if self.tail == None: temp = Node(item) self.tail = temp self.head = temp # DLL is not empty else: temp = Node(item) self.tail.next = temp temp.prev = self.tail self.tail = temp # Function to find the nodes # which have to be swapped def find(self, x, y): N1 = None N2 = None temp = self.head # Traversing the list while temp != None: if temp.data == x: N1 = temp elif temp.data == y: N2 = temp temp = temp.next return pair(N1, N2) # Function to swap the nodes # consisting of x and y def swap(self, x, y): # Edge Cases if self.head == None or self.head.next == None or x == y: return # Finding the Nodes p = self.find(x, y) Node1 = p.first Node2 = p.second if Node1 == self.head: self.head = Node2 elif Node2 == self.head: self.head = Node1 if Node1 == self.tail: self.tail = Node2 elif Node2 == self.tail: self.tail = Node1 # Swapping Node1 and Node2 temp = None temp = Node1.next Node1.next = Node2.next Node2.next = temp if Node1.next != None: Node1.next.prev = Node1 if Node2.next != None: Node2.next.prev = Node2 temp = Node1.prev Node1.prev = Node2.prev Node2.prev = temp if Node1.prev != None: Node1.prev.next = Node1 if Node2.prev != None: Node2.prev.next = Node2 # Driver Code if __name__ == '__main__': dll = DoublyLL() dll.push(1) dll.push(8) dll.push(7) dll.push(9) dll.push(4) X = 1 Y = 4 print("Before Swapping:", end=" ") dll.print_list() dll.swap(X, Y) print("After Swapping:", end=" ") dll.print_list() # This code is contributed by Tapesh (tapeshdua420)
C#
// C# code to implement the above approach using System; public class GFG{ // Link list Node Class class Node { public int data; public Node prev; public Node next; // Constructor function public Node(int data) { this.data = data; this.prev = null; this.next = null; } }; class pair { public Node first, second; public pair(Node first, Node second) { this.first = first; this.second = second; } } // Function to print linked list static void print(Node head) { Node temp = head; // Iterate until node is NOT null while (temp != null) { Console.Write(temp.data+ " "); temp = temp.next; } Console.WriteLine(); } static Node head; static Node tail; // Function to push a node in DLL static void push( int item) { // DLL is empty if (tail == null) { Node temp = new Node(item); tail = temp; head = temp; } // DLL is not empty else { Node temp = new Node(item); tail.next = temp; temp.prev = tail; tail = temp; } } // Function to find the nodes // which have to be swapped static pair find(int x, int y) { Node N1 = null; Node N2 = null; Node temp = head; // Traversing the list while (temp != null) { if (temp.data == x) N1 = temp; else if (temp.data == y) N2 = temp; temp = temp.next; } return new pair(N1, N2); } // Function to swap the nodes // consisting of x and y static void swap( int x, int y) { // Edge Cases if (head == null || head.next == null || x == y) return; // Finding the Nodes pair p = find( x, y); Node Node1 = p.first; Node Node2 = p.second; if (Node1 == head) head = Node2; else if (Node2 == head) head = Node1; if (Node1 == tail) tail = Node2; else if (Node2 == tail) tail = Node1; // Swapping Node1 and Node2 Node temp; temp = Node1.next; Node1.next = Node2.next; Node2.next = temp; if (Node1.next != null) Node1.next.prev = Node1; if (Node2.next != null) Node2.next.prev = Node2; temp = Node1.prev; Node1.prev = Node2.prev; Node2.prev = temp; if (Node1.prev != null) Node1.prev.next = Node1; if (Node2.prev != null) Node2.prev.next = Node2; } // Driver Code public static void Main(String[] args) { head = null; tail = null; push( 1); push( 8); push(7); push(9); push( 4); int X = 1, Y = 4; Console.Write("Before Swapping: "); print(head); swap( X, Y); Console.Write("After Swapping: "); print(head); } } // This code contributed by shikhasingrajput
Javascript
<script> // JavaScript code to implement the above approach // Link list Node Class class Node{ constructor(data){ this.data = data this.prev = null this.next = null } } class pair{ constructor(first, second){ this.first = first this.second = second } } class DoublyLL{ constructor(){ this.head = null this.tail = null } // Function to print linked list print_list(){ let temp = this.head while(temp){ document.write(temp.data," ") temp = temp.next } document.write("</br>") } // Function to push a node in DLL push(item){ // DLL is empty if(this.tail == null){ let temp = new Node(item) this.tail = temp this.head = temp } // DLL is not empty else{ let temp = new Node(item) this.tail.next = temp temp.prev = this.tail this.tail = temp } } // Function to find the nodes // which have to be swapped find(x, y){ let N1 = null let N2 = null let temp = this.head // Traversing the list while(temp != null){ if(temp.data == x) N1 = temp else if(temp.data == y) N2 = temp temp = temp.next } return new pair(N1, N2) } // Function to swap the nodes // consisting of x and y swap(x, y){ // Edge Cases if(this.head == null || this.head.next == null || x == y) return // Finding the Nodes let p = this.find(x, y) let Node1 = p.first let Node2 = p.second if(Node1 == this.head) this.head = Node2 else if(Node2 == this.head) this.head = Node1 if(Node1 == this.tail) this.tail = Node2 else if(Node2 == this.tail) this.tail = Node1 // Swapping Node1 and Node2 let temp = null temp = Node1.next Node1.next = Node2.next Node2.next = temp if(Node1.next != null) Node1.next.prev = Node1 if(Node2.next != null) Node2.next.prev = Node2 temp = Node1.prev Node1.prev = Node2.prev Node2.prev = temp if(Node1.prev != null) Node1.prev.next = Node1 if(Node2.prev != null) Node2.prev.next = Node2 } } // Driver Code let dll = new DoublyLL() dll.push(1) dll.push(8) dll.push(7) dll.push(9) dll.push(4) let X = 1 let Y = 4 document.write("Before Swapping:"," ") dll.print_list() dll.swap(X, Y) document.write("After Swapping:"," ") dll.print_list() // This code is contributed by shinjanpatra </script>
Before Swapping: 1 8 7 9 4 After Swapping: 4 8 7 9 1
Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por akashjha2671 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA