给定一个单链表，编写一个函数来成对交换元素。
null
输入：1->2->3->4->5->6->NULL 输出：2->1->4->3->6->5->NULL
输入：1->2->3->4->5->NULL 输出：2->1->4->3->5->NULL
输入：1->NULL 输出：1->NULL
例如，如果链表是1->2->3->4->5，则函数应将其更改为2->1->4->3->5，如果链表是，则函数应将其更改为。
方法1（迭代） 从头部节点开始，遍历列表。在遍历每个节点的交换数据及其下一个节点的数据时。
以下是上述方法的实施情况：
C++
// C++ program to pairwise swap elements // in a given linked list #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 */ void pairWiseSwap(Node* head) { Node* temp = head; /* Traverse further only if there are at-least two nodes left */ while (temp != NULL && temp->next != NULL) { /* Swap data of node with its next node's data */ swap(temp->data, temp->next->data); /* Move temp by 2 for the next pair */ temp = temp->next->next; } } /* 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 */ push(&start, 5); push(&start, 4); push(&start, 3); push(&start, 2); push(&start, 1); cout << "Linked list " << "before calling pairWiseSwap()" ; printList(start); pairWiseSwap(start); cout << "Linked list " << "after calling pairWiseSwap()" ; printList(start); return 0; } // This code is contributed // by rathbhupendra |
C
/* C program to pairwise swap elements in a given linked list */ #include <stdio.h> #include <stdlib.h> /* A linked list node */ struct Node { int data; struct Node* next; }; /*Function to swap two integers at addresses a and b */ void swap( int * a, int * b); /* Function to pairwise swap elements of a linked list */ void pairWiseSwap( struct Node* head) { struct Node* temp = head; /* Traverse further only if there are at-least two nodes left */ while (temp != NULL && temp->next != NULL) { /* Swap data of node with its next node's data */ swap(&temp->data, &temp->next->data); /* Move temp by 2 for the next pair */ temp = temp->next->next; } } /* UTILITY FUNCTIONS */ /* Function to swap two integers */ void swap( int * a, int * b) { int temp; temp = *a; *a = *b; *b = temp; } /* 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 */ 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); return 0; } |
JAVA
// Java program to pairwise swap elements of a linked list class LinkedList { Node head; // head of list /* Linked list Node*/ class Node { int data; Node next; Node( int d) { data = d; next = null ; } } void pairWiseSwap() { Node temp = head; /* Traverse only till there are atleast 2 nodes left */ while (temp != null && temp.next != null ) { /* Swap the data */ int k = temp.data; temp.data = temp.next.data; temp.next.data = k; temp = temp.next.next; } } /* Utility functions */ /* Inserts a new Node at front of the list. */ public void push( int new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; } /* Function to print linked list */ void printList() { Node temp = head; while (temp != null ) { System.out.print(temp.data + " " ); temp = temp.next; } System.out.println(); } /* Driver program to test above functions */ public static void main(String args[]) { LinkedList llist = new LinkedList(); /* Created Linked List 1->2->3->4->5 */ llist.push( 5 ); llist.push( 4 ); llist.push( 3 ); llist.push( 2 ); llist.push( 1 ); System.out.println( "Linked List before calling pairWiseSwap() " ); llist.printList(); llist.pairWiseSwap(); System.out.println( "Linked List after calling pairWiseSwap() " ); llist.printList(); } } /* This code is contributed by Rajat Mishra */ |
python
# Python program to swap the elements of linked list pairwise # Node class class Node: # Constructor to initialize the node object def __init__( self , data): self .data = data self . next = None class LinkedList: # Function to initialize head def __init__( self ): self .head = None # Function to pairwise swap elements of a linked list def pairwiseSwap( self ): temp = self .head # There are no nodes in linked list if temp is None : return # Traverse furthethr only if there are at least two # left while (temp and temp. next ): # If both nodes are same, # no need to swap data if (temp.data ! = temp. next .data): # Swap data of node with its next node's data temp.data, temp. next .data = temp. next .data, temp.data # Move temp by 2 to the next pair temp = temp. next . next # Function to insert a new node at the beginning def push( self , new_data): new_node = Node(new_data) new_node. next = self .head self .head = new_node # Utility function to print the linked LinkedList def printList( self ): temp = self .head while (temp): print temp.data, temp = temp. next # Driver program llist = LinkedList() llist.push( 5 ) llist.push( 4 ) llist.push( 3 ) llist.push( 2 ) llist.push( 1 ) print "Linked list before calling pairWiseSwap() " llist.printList() llist.pairwiseSwap() print "Linked list after calling pairWiseSwap()" llist.printList() # This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
// C# program to pairwise swap elements of a linked list using System; class LinkedList { Node head; // head of list /* Linked list Node*/ public class Node { public int data; public Node next; public Node( int d) { data = d; next = null ; } } void pairWiseSwap() { Node temp = head; /* Traverse only till there are atleast 2 nodes left */ while (temp != null && temp.next != null ) { /* Swap the data */ int k = temp.data; temp.data = temp.next.data; temp.next.data = k; temp = temp.next.next; } } /* Utility functions */ /* Inserts a new Node at front of the list. */ public void push( int new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; } /* Function to print linked list */ void printList() { Node temp = head; while (temp != null ) { Console.Write(temp.data + " " ); temp = temp.next; } Console.WriteLine(); } /* Driver program to test above functions */ public static void Main(String[] args) { LinkedList llist = new LinkedList(); /* Created Linked List 1->2->3->4->5 */ llist.push(5); llist.push(4); llist.push(3); llist.push(2); llist.push(1); Console.WriteLine( "Linked List before calling pairWiseSwap() " ); llist.printList(); llist.pairWiseSwap(); Console.WriteLine( "Linked List after calling pairWiseSwap() " ); llist.printList(); } } // This code is contributed by Arnab Kundu |
Javascript
<script> // JavaScript program to pairwise swap // elements of a linked list var head; // head of list /* Linked list Node */ class Node { constructor(val) { this .data = val; this .next = null ; } } function pairWiseSwap() { var temp = head; /* Traverse only till there are atleast 2 nodes left */ while (temp != null && temp.next != null ) { /* Swap the data */ var k = temp.data; temp.data = temp.next.data; temp.next.data = k; temp = temp.next.next; } } /* Utility functions */ /* Inserts a new Node at front of the list. */ function push(new_data) { /* * 1 & 2: Allocate the Node & Put in the data */ var new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; } /* Function to print linked list */ function printList() { var temp = head; while (temp != null ) { document.write(temp.data + " " ); temp = temp.next; } document.write( "<br/>" ); } /* Driver program to test above functions */ /* Created Linked List 1->2->3->4->5 */ push(5); push(4); push(3); push(2); push(1); document.write( "Linked List before calling pairWiseSwap() <br/>" ); printList(); pairWiseSwap(); document.write( "Linked List after calling pairWiseSwap()<br/> " ); printList(); // This code is contributed by todaysgaurav </script> |
输出
Linked list before calling pairWiseSwap()1 2 3 4 5 Linked list after calling pairWiseSwap()2 1 4 3 5
时间复杂性： O（n）
方法2（递归） 如果链表中有2个或多于2个节点，则交换前两个节点，并递归调用列表的其余部分。
下图是上述方法的试运行：
![图片[1]-给定链表的成对交换元素-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/cdn-uploads/20190624140737/Pairwise-swap-elements-of-a-given-linked-list.png)
以下是上述方法的实施情况：
C
/* Recursive function to pairwise swap elements of a linked list */ void pairWiseSwap( struct node* head) { /* There must be at-least two nodes in the list */ if (head != NULL && head->next != NULL) { /* Swap the node's data with data of next node */ swap(head->data, head->next->data); /* Call pairWiseSwap() for rest of the list */ pairWiseSwap(head->next->next); } } |
JAVA
/* Recursive function to pairwise swap elements of a linked list */ static void pairWiseSwap(node head) { /* There must be at-least two nodes in the list */ if (head != null && head.next != null ) { /* Swap the node's data with data of next node */ swap(head.data, head.next.data); /* Call pairWiseSwap() for rest of the list */ pairWiseSwap(head.next.next); } } // This code contributed by aashish1995 |
蟒蛇3
# Recursive function to pairwise swap elements of a linked list def pairWiseSwap(head): # There must be at-least two nodes in the list if (head ! = None and head. next ! = None ): # Swap the node's data with data of next node swap(head.data, head. next .data); # Call pairWiseSwap() for rest of the list pairWiseSwap(head. next . next ); # This code is contributed by _saurabh_jaiswal |
C#
/* Recursive function to pairwise swap elements of a linked list */ static void pairWiseSwap(node head) { /* There must be at-least two nodes in the list */ if (head != null && head.next != null ) { /* Swap the node's data with data of next node */ swap(head.data, head.next.data); /* Call pairWiseSwap() for rest of the list */ pairWiseSwap(head.next.next); } } // This code contributed by aashish1995 |
Javascript
<script> /* Recursive function to pairwise swap elements of a linked list */ function pairWiseSwap(head) { /* There must be at-least two nodes in the list */ if (head != null && head.next != null ) { /* Swap the node's data with data of next node */ swap(head.data, head.next.data); /* Call pairWiseSwap() for rest of the list */ pairWiseSwap(head.next.next); } } // This code is contributed by avanitrachhadiya2155 </script> |
时间复杂性： O（n）
该解决方案提供了节点数据交换。如果数据包含许多字段，则会有许多交换操作。看见 这 用于更改链接而不是交换数据的实现。
如果您在上述代码/算法中发现任何错误，请写评论，或者找到其他方法来解决相同的问题。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
