给定一个单链表，编写一个函数来成对交换元素。例如，如果链表为1->2->3->4->5->6->7，则函数应将其更改为2->1->4->3->6->5->7，如果链表为1->2->3->4->5->6，则函数应将其更改为2->1->4->3->6->5
null
这个问题已经讨论过了 在这里 .提供的解决方案交换节点的数据。如果数据包含许多字段，则会有许多交换操作。所以一般来说，改变链接是个更好的主意。以下是更改链接而不是交换数据的实现。
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 */ class node { public : int data; node* next; }; /* Function to pairwise swap elements of a linked list. It returns head of the modified list, so return value of this node must be assigned */ 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; // Initialize previous and current pointers node* prev = head; node* curr = head->next; head = curr; // Change head before proceeding // Traverse the list while ( true ) { node* next = curr->next; curr->next = prev; // Change next of // current as previous node // If next NULL or next is the last node if (next == NULL || next->next == NULL) { prev->next = next; break ; } // Change next of previous to next of next prev->next = next->next; // Update previous and curr prev = next; curr = prev->next; } return head; } /* Function to add a node at the beginning of Linked List */ void push(node** head_ref, int new_data) { /* allocate node */ node* new_node = new node(); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print nodes in a given linked list */ void printList(node* node) { while (node != NULL) { cout << node->data << " " ; node = node->next; } } /* Driver code */ int main() { 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); cout << "Linked list before " << "calling pairWiseSwap() " ; printList(start); start = pairWiseSwap(start); // NOTE THIS CHANGE cout << "Linked list after calling" << "pairWiseSwap() " ; printList(start); return 0; } // This code is contributed by Manoj N |
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 <stdbool.h> #include <stdio.h> #include <stdlib.h> /* A linked list node */ struct Node { int data; struct Node* next; }; /* Function to pairwise swap elements of a linked list */ void pairWiseSwap( struct Node** head) { // If linked list is empty or there is only one node in list if (*head == NULL || (*head)->next == NULL) return ; // Initialize previous and current pointers struct Node* prev = *head; struct Node* curr = (*head)->next; *head = curr; // Change head before proceeding // Traverse the list while ( true ) { struct Node* next = curr->next; curr->next = prev; // Change next of current as previous node // If next NULL or next is the last node if (next == NULL || next->next == NULL) { prev->next = next; break ; } // Change next of previous to next next prev->next = next->next; // Update previous and curr prev = next; curr = prev->next; } } /* Function to add a node at the beginning of Linked List */ void push( struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*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 ( " Linked list before calling pairWiseSwap() " ); printList(start); pairWiseSwap(&start); printf ( " Linked list after calling pairWiseSwap() " ); printList(start); getchar (); return 0; } |
JAVA
// Java program to swap elements of linked list by changing links class LinkedList { static Node head; static class Node { int data; Node next; Node( int d) { data = d; next = null ; } } /* Function to pairwise swap elements of a linked list */ Node pairWiseSwap(Node node) { // If linked list is empty or there is only one node in list if (node == null || node.next == null ) { return node; } // Initialize previous and current pointers Node prev = node; Node curr = node.next; node = curr; // Change head before proceeding // Traverse the list while ( true ) { Node next = curr.next; curr.next = prev; // Change next of current as previous node // If next NULL or next is the last node if (next == null || next.next == null ) { prev.next = next; break ; } // Change next of previous to next next prev.next = next.next; // Update previous and curr prev = next; curr = prev.next; } return node; } /* Function to print nodes in a given linked list */ void printList(Node node) { while (node != null ) { System.out.print(node.data + " " ); node = node.next; } } // Driver program to test above functions public static void main(String[] args) { /* The constructed linked list is: 1->2->3->4->5->6->7 */ LinkedList list = new LinkedList(); list.head = new Node( 1 ); list.head.next = new Node( 2 ); list.head.next.next = new Node( 3 ); list.head.next.next.next = new Node( 4 ); list.head.next.next.next.next = new Node( 5 ); list.head.next.next.next.next.next = new Node( 6 ); list.head.next.next.next.next.next.next = new Node( 7 ); System.out.println( "Linked list before calling pairwiseSwap() " ); list.printList(head); Node st = list.pairWiseSwap(head); System.out.println( "" ); System.out.println( "Linked list after calling pairwiseSwap() " ); list.printList(st); System.out.println( "" ); } } // This code has been contributed by Mayank Jaiswal |
Python3
# Python3 program to swap elements of # linked list by changing links # Linked List Node class Node: def __init__( self , data): self .data = data self . next = None # Create and Handle list operations class LinkedList: def __init__( self ): # Head of list self .head = None # Add data to list def addToList( self , data): newNode = Node(data) if self .head is None : self .head = newNode return last = self .head while last. next : last = last. next last. next = newNode # Function to print nodes # in a given linked list def __str__( self ): linkedListStr = "" temp = self .head while temp: linkedListStr = (linkedListStr + str (temp.data) + " " ) temp = temp. next return linkedListStr # Function to pairwise swap elements # of a linked list. It returns head of # the modified list, so return value # of this node must be assigned def pairWiseSwap( self ): # If list is empty or with one node if ( self .head is None or self .head. next is None ): return # Initialize previous and current pointers prevNode = self .head currNode = self .head. next # Change head node self .head = currNode # Traverse the list while True : nextNode = currNode. next # Change next of current # node to previous node currNode. next = prevNode # If next node is the last node if nextNode. next is None : prevNode. next = nextNode break # Change next of previous to # next of next prevNode. next = nextNode. next # Update previous and current nodes prevNode = nextNode currNode = prevNode. next # Driver Code linkedList = LinkedList() linkedList.addToList( 1 ) linkedList.addToList( 2 ) linkedList.addToList( 3 ) linkedList.addToList( 4 ) linkedList.addToList( 5 ) linkedList.addToList( 6 ) linkedList.addToList( 7 ) print ( "Linked list before calling" "pairwiseSwap() " , linkedList) linkedList.pairWiseSwap() print ( "Linked list after calling " "pairwiseSwap() " , linkedList) # This code is contributed by AmiyaRanjanRout |
C#
// C# program to swap elements of // linked list by changing links using System; public class LinkedList { Node head; public class Node { public int data; public Node next; public Node( int d) { data = d; next = null ; } } /* Function to pairwise swap elements of a linked list */ Node pairWiseSwap(Node node) { // If linked list is empty or there // is only one node in list if (node == null || node.next == null ) { return node; } // Initialize previous and current pointers Node prev = node; Node curr = node.next; // Change head before proceeeding node = curr; // Traverse the list while ( true ) { Node next = curr.next; // Change next of current as previous node curr.next = prev; // If next NULL or next is the last node if (next == null || next.next == null ) { prev.next = next; break ; } // Change next of previous to next of next prev.next = next.next; // Update previous and curr prev = next; curr = prev.next; } return node; } /* Function to print nodes in a given linked list */ void printList(Node node) { while (node != null ) { Console.Write(node.data + " " ); node = node.next; } } // Driver code public static void Main(String[] args) { /* The constructed linked list is: 1->2->3->4->5->6->7 */ LinkedList list = new LinkedList(); list.head = new Node(1); list.head.next = new Node(2); list.head.next.next = new Node(3); list.head.next.next.next = new Node(4); list.head.next.next.next.next = new Node(5); list.head.next.next.next.next.next = new Node(6); list.head.next.next.next.next.next.next = new Node(7); Console.WriteLine( "Linked list before calling pairwiseSwap() " ); list.printList(list.head); Node st = list.pairWiseSwap(list.head); Console.WriteLine( "" ); Console.WriteLine( "Linked list after calling pairwiseSwap() " ); list.printList(st); Console.WriteLine( "" ); } } // This code contributed by Rajput-Ji |
Javascript
<script> // javascript program to swap elements of linked list by changing links var head; class Node { constructor(val) { this .data = val; this .next = null ; } } /* Function to pairwise swap elements of a linked list */ function pairWiseSwap(node) { // If linked list is empty or there is only one node in list if (node == null || node.next == null ) { return node; } // Initialize previous and current pointers var prev = node; var curr = node.next; node = curr; // Change head before proceeding // Traverse the list while ( true ) { var next = curr.next; curr.next = prev; // Change next of current as previous node // If next NULL or next is the last node if (next == null || next.next == null ) { prev.next = next; break ; } // Change next of previous to next next prev.next = next.next; // Update previous and curr prev = next; curr = prev.next; } return node; } /* Function to print nodes in a given linked list */ function printList(node) { while (node != null ) { document.write(node.data + " " ); node = node.next; } } // Driver program to test above functions /* * The constructed linked list is: 1->2->3->4->5->6->7 */ 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); head.next.next.next.next.next = new Node(6); head.next.next.next.next.next.next = new Node(7); document.write( "Linked list before calling pairwiseSwap() " ); printList(head); var st = pairWiseSwap(head); document.write( "<br/>" ); document.write( "Linked list after calling pairwiseSwap() " ); printList(st); document.write( "" ); // This code contributed by aashish1995 </script> |
输出：
Linked list before calling pairWiseSwap() 1 2 3 4 5 6 7 Linked list after calling pairWiseSwap() 2 1 4 3 6 5 7
时间复杂性： 上述程序的时间复杂度为O（n），其中n是给定链表中的节点数。while循环遍历给定的链表。
以下是 递归实现 同样的方法。我们更改前两个节点，然后重复执行剩余的列表。感谢geek和omer salem提出了这种方法。
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 */ class node { public : int data; node* next; }; /* Function to pairwise swap elements of a linked list. It returns head of the modified list, so return value of this node must be assigned */ node* pairWiseSwap(node* head) { // Base Case: The list is empty or has only one node if (head == NULL || head->next == NULL) return head; // Store head of list after two nodes node* remaining = head->next->next; // Change head node* newhead = head->next; // Change next of second node head->next->next = head; // Recur for remaining list and change next of head head->next = pairWiseSwap(remaining); // Return new head of modified list return newhead; } /* Function to add a node at the beginning of Linked List */ void push(node** head_ref, int new_data) { /* allocate node */ node* new_node = new node(); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print nodes in a given linked list */ void printList(node* node) { while (node != NULL) { cout << node->data << " " ; node = node->next; } } /* Driver program to test above function */ int main() { 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); cout << "Linked list before calling pairWiseSwap() " ; printList(start); start = pairWiseSwap(start); // NOTE THIS CHANGE cout << "Linked list after calling pairWiseSwap() " ; printList(start); return 0; } // This is code is contributed by rathbhupendra |
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 <stdbool.h> #include <stdio.h> #include <stdlib.h> /* A linked list node */ struct node { int data; struct node* next; }; /* Function to pairwise swap elements of a linked list. It returns head of the modified list, so return value of this node must be assigned */ struct node* pairWiseSwap( struct node* head) { // Base Case: The list is empty or has only one node if (head == NULL || head->next == NULL) return head; // Store head of list after two nodes struct node* remaining = head->next->next; // Change head struct node* newhead = head->next; // Change next of second node head->next->next = head; // Recur for remaining list and change next of head head->next = pairWiseSwap(remaining); // Return new head of modified list return newhead; } /* Function to add a node at the beginning of Linked List */ void push( struct node** head_ref, int new_data) { /* allocate node */ struct node* new_node = ( struct node*) malloc ( sizeof ( struct node)); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*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 ( " Linked list before calling pairWiseSwap() " ); printList(start); start = pairWiseSwap(start); // NOTE THIS CHANGE printf ( " Linked list after calling pairWiseSwap() " ); printList(start); return 0; } |
JAVA
// Java program to swap elements of linked list by changing links class LinkedList { static Node head; static class Node { int data; Node next; Node( int d) { data = d; next = null ; } } /* Function to pairwise swap elements of a linked list. It returns head of the modified list, so return value of this node must be assigned */ Node pairWiseSwap(Node node) { // Base Case: The list is empty or has only one node if (node == null || node.next == null ) { return node; } // Store head of list after two nodes Node remaining = node.next.next; // Change head Node newhead = node.next; // Change next of second node node.next.next = node; // Recur for remaining list and change next of head node.next = pairWiseSwap(remaining); // Return new head of modified list return newhead; } /* Function to print nodes in a given linked list */ void printList(Node node) { while (node != null ) { System.out.print(node.data + " " ); node = node.next; } } // Driver program to test above functions public static void main(String[] args) { /* The constructed linked list is: 1->2->3->4->5->6->7 */ LinkedList list = new LinkedList(); list.head = new Node( 1 ); list.head.next = new Node( 2 ); list.head.next.next = new Node( 3 ); list.head.next.next.next = new Node( 4 ); list.head.next.next.next.next = new Node( 5 ); list.head.next.next.next.next.next = new Node( 6 ); list.head.next.next.next.next.next.next = new Node( 7 ); System.out.println( "Linked list before calling pairwiseSwap() " ); list.printList(head); head = list.pairWiseSwap(head); System.out.println( "" ); System.out.println( "Linked list after calling pairwiseSwap() " ); list.printList(head); System.out.println( "" ); } } |
Python3
# Python3 program to pairwise swap # linked list using recursive method # Linked List Node class Node: def __init__( self , data): self .data = data self . next = None # Create and Handle list operations class LinkedList: def __init__( self ): # Head of list self .head = None # Add data to list def addToList( self , data): newNode = Node(data) if self .head is None : self .head = newNode return last = self .head while last. next : last = last. next last. next = newNode # Function to print nodes in # a given linked list def __str__( self ): linkedListStr = "" temp = self .head while temp: linkedListStr = (linkedListStr + str (temp.data) + " " ) temp = temp. next return linkedListStr # Function to pairwise swap elements of # a linked list.It returns head of the # modified list, so return value # of this node must be assigned def pairWiseSwap( self , node): # If list is empty or with one node if node is None or node. next is None : return node # Store head of list after 2 nodes remaining = node. next . next # Change head newHead = node. next # Change next to second node node. next . next = node # Recur for remaining list and # change next of head node. next = self .pairWiseSwap(remaining) # Return new head of modified list return newHead # Driver Code linkedList = LinkedList() linkedList.addToList( 1 ) linkedList.addToList( 2 ) linkedList.addToList( 3 ) linkedList.addToList( 4 ) linkedList.addToList( 5 ) linkedList.addToList( 6 ) linkedList.addToList( 7 ) print ( "Linked list before calling " "pairwiseSwap() " , linkedList) linkedList.head = linkedList.pairWiseSwap( linkedList.head) print ( "Linked list after calling " "pairwiseSwap() " , linkedList) # This code is contributed by AmiyaRanjanRout |
C#
// C# program to swap elements // of linked list by changing links using System; public class LinkedList { Node head; class Node { public int data; public Node next; public Node( int d) { data = d; next = null ; } } /* Function to pairwise swap elements of a linked list. It returns head of the modified list, so return value of this node must be assigned */ Node pairWiseSwap(Node node) { // Base Case: The list is empty // or has only one node if (node == null || node.next == null ) { return node; } // Store head of list after two nodes Node remaining = node.next.next; // Change head Node newhead = node.next; // Change next of second node node.next.next = node; // Recur for remaining list // and change next of head node.next = pairWiseSwap(remaining); // Return new head of modified list return newhead; } /* Function to print nodes in a given linked list */ void printList(Node node) { while (node != null ) { Console.Write(node.data + " " ); node = node.next; } } // Driver program to test above functions public static void Main() { /* The constructed linked list is: 1->2->3->4->5->6->7 */ LinkedList list = new LinkedList(); list.head = new Node(1); list.head.next = new Node(2); list.head.next.next = new Node(3); list.head.next.next.next = new Node(4); list.head.next.next.next.next = new Node(5); list.head.next.next.next.next.next = new Node(6); list.head.next.next.next.next.next.next = new Node(7); Console.WriteLine( "Linked list before calling pairwiseSwap() " ); list.printList(list.head); list.head = list.pairWiseSwap(list.head); Console.WriteLine( "" ); Console.WriteLine( "Linked list after calling pairwiseSwap() " ); list.printList(list.head); Console.WriteLine( "" ); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // javascript program to swap elements of linked list by changing links var head; class Node { constructor(val) { this .data = val; this .next = null ; } } /* * Function to pairwise swap elements of a linked It returns head of the * modified list, so return value of this node must be assigned */ function pairWiseSwap(node) { // Base Case: The list is empty or has only one node if (node == null || node.next == null ) { return node; } // Store head of list after two nodes var remaining = node.next.next; // Change head var newhead = node.next; // Change next of second node node.next.next = node; // Recur for remaining list and change next of head node.next = pairWiseSwap(remaining); // Return new head of modified list return newhead; } /* Function to print nodes in a given linked list */ function printList(node) { while (node != null ) { document.write(node.data + " " ); node = node.next; } } // Driver program to test above functions /* * The constructed linked list is: 1->2->3->4->5->6->7 */ 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); head.next.next.next.next.next = new Node(6); head.next.next.next.next.next.next = new Node(7); document.write( "Linked list before calling pairwiseSwap() " ); printList(head); head = pairWiseSwap(head); document.write( "<br/>" ); document.write( "Linked list after calling pairwiseSwap() " ); printList(head); document.write( "" ); // This code contributed by umadevi9616 </script> |
输出：
Linked list before calling pairWiseSwap() 1 2 3 4 5 6 7 Linked list after calling pairWiseSwap() 2 1 4 3 6 5 7
通过改变指针|集2，成对交换链表的相邻节点 本文由 乔塔姆·库马尔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
