Dada una lista enlazada individualmente, escriba una función para intercambiar elementos por pares.
Input : 1->2->3->4->5->6->7 Output : 2->1->4->3->6->5->7, Input : 1->2->3->4->5->6 Output : 2->1->4->3->6->5
Se ha discutido una solución conjunto 1 . Aquí se discute una solución más simple. Cambiamos explícitamente los punteros de los dos primeros Nodes y luego arreglamos los Nodes restantes.
C++
/* This program swaps the nodes of linked list rather than swapping the field from the nodes. Imagine a case where a node contains many fields, there will be plenty of unnecessary swap calls. */ #include<bits/stdc++.h> using namespace std; /* A linked list node */ struct Node { int data; struct Node *next; }; /* Function to pairwise swap elements of a linked list */ Node *pairWiseSwap(Node *head) { // If linked list is empty or there is only // one node in list if (head == NULL || head->next == NULL) return head; // Fix the head and its next explicitly to // avoid many if else in while loop Node *curr = head->next->next; Node *prev = head; head = head->next; head->next = prev; // Fix remaining nodes while (curr != NULL && curr->next != NULL) { prev->next = curr->next; prev = curr; Node *next = curr->next->next; curr->next->next = curr; curr = next; } prev->next = curr; return head; } /* Function to add a node at the beginning of Linked List */ void push(struct Node** head_ref, int new_data) { struct Node* new_node = new Node; new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } /* Function to print nodes in a given linked list */ void printList(struct Node *node) { while (node != NULL) { printf("%d ", node->data); node = node->next; } } /* Driver program to test above function */ int main() { struct Node *start = NULL; /* The constructed linked list is: 1->2->3->4->5->6->7 */ push(&start, 7); push(&start, 6); push(&start, 5); push(&start, 4); push(&start, 3); push(&start, 2); push(&start, 1); printf("\n Linked list before calling pairWiseSwap() "); printList(start); start = pairWiseSwap(start); printf("\n Linked list after calling pairWiseSwap() "); printList(start); return 0; }
Java
/* This program swaps the nodes of linked list rather than swapping the field from the nodes. Imagine a case where a node contains many fields, there will be plenty of unnecessary swap calls. */ class GfG { /* A linked list node */ static class Node { int data; Node next; } static Node head = null; /* Function to pairwise swap elements of a linked list */ static Node pairWiseSwap(Node head) { // If linked list is empty or there is only // one node in list if (head == null || head.next == null) return head; // Fix the head and its next explicitly to // avoid many if else in while loop Node curr = head.next.next; Node prev = head; head = head.next; head.next = prev; // Fix remaining nodes while (curr != null && curr.next != null) { prev.next = curr.next; prev = curr; Node next = curr.next.next; curr.next.next = curr; curr = next; } prev.next = curr; return head; } /* Function to add a node at the beginning of Linked List */ static void push(int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = (head); (head) = new_node; } /* Function to print nodes in a given linked list */ static void printList(Node node) { while (node != null) { System.out.print(node.data + " "); node = node.next; } } /* Driver code */ public static void main(String[] args) { //Node head = null; /* The constructed linked list is: 1->2->3->4->5->6->7 */ push( 7); push( 6); push( 5); push( 4); push(3); push( 2); push( 1); System.out.print("\n Linked list before calling pairWiseSwap() "); printList(head); Node start = pairWiseSwap(head); System.out.print("\n Linked list after calling pairWiseSwap() "); printList(start); } } // This code is contributed by Prerna Saini.
Python3
# This program swaps the nodes of linked list # rather than swapping the field from the nodes. # Imagine a case where a node contains many # fields, there will be plenty of unnecessary # swap calls. # A linked list node class Node: def __init__(self, data): self.data = data self.next = None # Function to pairwise swap elements of a # linked list def pairWiseSwap(head): # If linked list is empty or there is only # one node in list if (head == None or head.next == None): return head # Fix the head and its next explicitly to # avoid many if else in while loop curr = head.next.next prev = head head = head.next head.next = prev # Fix remaining nodes while (curr != None and curr.next != None): prev.next = curr.next prev = curr next = curr.next.next curr.next.next = curr curr = next prev.next = curr return head # Function to add a node at the beginning # of Linked List def push(head_ref, new_data): new_node = Node(new_data) new_node.next = (head_ref) (head_ref) = new_node return head_ref # Function to print nodes in a # given linked list def printList(node): while (node != None): print(node.data, end = ' ') node = node.next # Driver Code if __name__=='__main__': start = None # The constructed linked list is: # 1.2.3.4.5.6.7 start = push(start, 7) start = push(start, 6) start = push(start, 5) start = push(start, 4) start = push(start, 3) start = push(start, 2) start = push(start, 1) print("\nLinked list before " "calling pairWiseSwap() ", end = '') printList(start) start = pairWiseSwap(start) print("\nLinked list after calling " "pairWiseSwap() ", end = '') printList(start) # This code is contributed by rutvik_56
C#
/* This program swaps the nodes of linked list rather than swapping the field from the nodes. Imagine a case where a node contains many fields, there will be plenty of unnecessary swap calls. */ using System; class GfG { /* A linked list node */ class Node { public int data; public Node next; } static Node head = null; /* Function to pairwise swap elements of a linked list */ static Node pairWiseSwap(Node head) { // If linked list is empty or there // is only one node in list if (head == null || head.next == null) return head; // Fix the head and its next explicitly to // avoid many if else in while loop Node curr = head.next.next; Node prev = head; head = head.next; head.next = prev; // Fix remaining nodes while (curr != null && curr.next != null) { prev.next = curr.next; prev = curr; Node next = curr.next.next; curr.next.next = curr; curr = next; } prev.next = curr; return head; } /* Function to add a node at the beginning of Linked List */ static void push(int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = (head); (head) = new_node; } /* Function to print nodes in a given linked list */ static void printList(Node node) { while (node != null) { Console.Write(node.data + " "); node = node.next; } } /* Driver code */ public static void Main() { //Node head = null; /* The constructed linked list is: 1->2->3->4->5->6->7 */ push( 7); push( 6); push( 5); push( 4); push(3); push( 2); push( 1); Console.Write("\n Linked list before" + "calling pairWiseSwap() "); printList(head); Node start = pairWiseSwap(head); Console.Write("\n Linked list after" + "calling pairWiseSwap() "); printList(start); } } // This code is contributed by PrinciRaj1992
Javascript
<script> /* This program swaps the nodes of linked list rather than swapping the field from the nodes. Imagine a case where a node contains many fields, there will be plenty of unnecessary swap calls. */ /* A linked list node */ class Node { constructor() { this.data = 0; this.next = null; } } var head = null; /* Function to pairwise swap elements of a linked list */ function pairWiseSwap(head) { // If linked list is empty or there // is only one node in list if (head == null || head.next == null) return head; // Fix the head and its next explicitly to // avoid many if else in while loop var curr = head.next.next; var prev = head; head = head.next; head.next = prev; // Fix remaining nodes while (curr != null && curr.next != null) { prev.next = curr.next; prev = curr; var next = curr.next.next; curr.next.next = curr; curr = next; } prev.next = curr; return head; } /* Function to add a node at the beginning of Linked List */ function push(new_data) { var new_node = new Node(); new_node.data = new_data; new_node.next = (head); (head) = new_node; } /* Function to print nodes in a given linked list */ function printList(node) { while (node != null) { document.write(node.data + " "); node = node.next; } } /* Driver code */ /* The constructed linked list is: 1->2->3->4->5->6->7 */ push( 7); push( 6); push( 5); push( 4); push(3); push( 2); push( 1); document.write("Linked list before" + "calling pairWiseSwap() "); printList(head); var start = pairWiseSwap(head); document.write("<br> Linked list after" + "calling pairWiseSwap() "); printList(start); </script>
Producción
Linked list before calling pairWiseSwap() 1 2 3 4 5 6 7 Linked list after calling pairWiseSwap() 2 1 4 3 6 5 7
Otro enfoque:
el enfoque aquí es usar los punteros dobles para que no necesitemos actualizar el puntero principal durante el intercambio por separado.
C
#include <stdio.h> #include <stdlib.h> // A nexted list node struct Node { int data; struct Node *next; }; /* Function to insert a node at the beginning */ void push(struct Node ** head_ref, int new_data) { struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } /* Utility function to print a singly linked list */ void printList(struct Node *head) { struct Node *temp = head; while (temp != NULL) { printf("%d ", temp->data); temp = temp->next; } printf("\n"); } // Function to swap adjacent nodes void swapPairs(struct Node **head) { //Loop until we reach the last node while(*head && (*head)->next) { struct Node *one = *head; struct Node *two = one->next->next; *head = one->next; one->next->next = one; one->next = two; head = &one->next; } } // Driver program to test above functions int main() { struct Node *head = NULL; push(&head, 6); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); printf("Actual List:\n"); printList(head); swapPairs(&head); printf("ModifiedLinked List:\n"); printList(head); getchar(); return 0; }
Producción
Actual List: 1 2 3 4 5 6 ModifiedLinked List: 2 1 4 3 6 5