Dada una lista vinculada, divida la lista vinculada en dos con Nodes alternativos.
Ejemplos:
Input : 1 2 3 4 5 6 7 Output : 1 3 5 7 2 4 6 Input : 1 4 5 6 Output : 1 5 4 6
Hemos discutido la división iterativa de la lista enlazada.
La idea es partir de dos Nodes primero y segundo. Llamemos a estos Nodes como ‘a’ y ‘b’. Nosotros recurrimos
C++
// CPP code to split linked list #include <bits/stdc++.h> using namespace std; // Node structure struct Node { int data; struct Node* next; }; // Function to push nodes // into linked list void push(Node** head, int new_data) { Node* new_node = new Node; new_node->data = new_data; new_node->next = (*head); (*head) = new_node; } // We basically remove link between 'a' // and its next. Similarly we remove link // between 'b' and its next. Then we recur // for remaining lists. void moveNode(Node* a, Node* b) { if (b == NULL || a == NULL) return; if (a->next != NULL) a->next = a->next->next; if (b->next != NULL) b->next = b->next->next; moveNode(a->next, b->next); } // function to split linked list void alternateSplitLinkedList(Node* head, Node** aRef, Node** bRef) { Node* curr = head; *aRef = curr; *bRef = curr->next; moveNode(*aRef, *bRef); } void display(Node* head) { Node* curr = head; while (curr != NULL) { printf("%d ", curr->data); curr = curr->next; } } // Driver code int main() { Node* head = NULL; Node *a = NULL, *b = NULL; push(&head, 7); push(&head, 6); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); alternateSplitLinkedList(head, &a, &b); printf("a : "); display(a); printf("\nb : "); display(b); return 0; }
Java
// Java code to split linked list class GFG { // Node structure static class Node { int data; Node next; }; // Function to push nodes // into linked list static Node push(Node head, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = (head); (head) = new_node; return head; } static Node a = null, b = null; // We basically remove link between 'a' // and its next. Similarly we remove link // between 'b' and its next. Then we recur // for remaining lists. static void moveNode(Node a, Node b) { if (b == null || a == null) return; if (a.next != null) a.next = a.next.next; if (b.next != null) b.next = b.next.next; moveNode(a.next, b.next); } // function to split linked list static void alternateSplitLinkedList(Node head) { Node curr = head; a = curr; b = curr.next; Node aRef = a, bRef = b; moveNode(aRef, bRef); } static void display(Node head) { Node curr = head; while (curr != null) { System.out.printf("%d ", curr.data); curr = curr.next; } } // Driver code public static void main(String args[]) { Node head = null; head = push(head, 7); head = push(head, 6); head = push(head, 5); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 1); alternateSplitLinkedList(head); System.out.printf("a : "); display(a); System.out.printf("\nb : "); display(b); } } // This code is contributed by Arnab Kundu
Python
# Python code to split linked list # Node structure class Node(object): def __init__(self, d): self.data = d self.next = None # Function to push nodes # into linked list def push( head, new_data) : new_node = Node(0) new_node.data = new_data new_node.next = (head) (head) = new_node return head a = None b = None # We basically remove link between 'a' # and its next. Similarly we remove link # between 'b' and its next. Then we recur # for remaining lists. def moveNode( a, b) : if (b == None or a == None) : return if (a.next != None) : a.next = a.next.next if (b.next != None) : b.next = b.next.next moveNode(a.next, b.next) # function to split linked list def alternateSplitLinkedList(head) : curr = head global a global b a = curr b = curr.next aRef = a bRef = b moveNode(aRef, bRef) return head; def display(head) : curr = head while (curr != None) : print( curr.data,end = " ") curr = curr.next # Driver code head = None head = push(head, 7) head = push(head, 6) head = push(head, 5) head = push(head, 4) head = push(head, 3) head = push(head, 2) head = push(head, 1) head=alternateSplitLinkedList(head) print("a : ",end="") display(a) print("\nb : ",end="") display(b) # This code is contributed by Arnab Kundu
C#
// C# code to split linked list using System; class GFG { // Node structure public class Node { public int data; public Node next; }; // Function to push nodes // into linked list static Node push(Node head, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = (head); (head) = new_node; return head; } static Node a = null, b = null; // We basically remove link between 'a' // and its next. Similarly we remove link // between 'b' and its next. Then we recur // for remaining lists. static void moveNode(Node a, Node b) { if (b == null || a == null) return; if (a.next != null) a.next = a.next.next; if (b.next != null) b.next = b.next.next; moveNode(a.next, b.next); } // function to split linked list static void alternateSplitLinkedList(Node head) { Node curr = head; a = curr; b = curr.next; Node aRef = a, bRef = b; moveNode(aRef, bRef); } static void display(Node head) { Node curr = head; while (curr != null) { Console.Write("{0} ", curr.data); curr = curr.next; } } // Driver code public static void Main(String []args) { Node head = null; head = push(head, 7); head = push(head, 6); head = push(head, 5); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 1); alternateSplitLinkedList(head); Console.Write("a : "); display(a); Console.Write("\nb : "); display(b); } } // This code is contributed by PrinciRaj1992
Javascript
<script> // JavaScript code to split linked list // Node structure class Node { constructor() { this.data = 0; this.next = null } }; // Function to push nodes // into linked list function push(head, new_data) { var new_node = new Node(); new_node.data = new_data; new_node.next = (head); (head) = new_node; return head; } var a = null, b = null; // We basically remove link between 'a' // and its next. Similarly we remove link // between 'b' and its next. Then we recur // for remaining lists. function moveNode(a, b) { if (b == null || a == null) return; if (a.next != null) a.next = a.next.next; if (b.next != null) b.next = b.next.next; moveNode(a.next, b.next); } // function to split linked list function alternateSplitLinkedList(head) { var curr = head; a = curr; b = curr.next; var aRef = a, bRef = b; moveNode(aRef, bRef); } function display(head) { var curr = head; while (curr != null) { document.write(curr.data+ " "); curr = curr.next; } } // Driver code var head = null; head = push(head, 7); head = push(head, 6); head = push(head, 5); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 1); alternateSplitLinkedList(head); document.write("a : "); display(a); document.write("<br>b : "); display(b); </script>
Producción:
a : 1 3 5 7 b : 2 4 6
Publicación traducida automáticamente
Artículo escrito por aditya1011 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA