给定一个单链表, 编写一个函数以成对替换元素。例如, 如果链接列表是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
这个问题曾经在lsbin((https://www.lsbin.com/tag/%e7%ae%97%e6%b3%95%e9%a2%98/)中探讨过了，那里提供的解决方案替换节点数据。如果数据蕴含许多字段, 将有许多替换操作。因而, 通常更改链接是一个更好的主见。以下是一个C实现, 它更改了链接而不是替换数据。
C ++
/* This program swaps the nodes oflinked list rather than swapping thefield from the nodes.Imagine a case where a node containsmany fields, there will be plentyof 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 elementsof a linked list. It returns head ofthe modified list, so return valueof 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 proceeeding // 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 head;} /* Function to add a node atthe begining 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 nodesin 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 << "nLinked list after calling" << "pairWiseSwap() " ; printList(start); return 0;} // This code is contributed by Manoj NC语言实现
/* This program swaps the nodes of linked list rather than swapping thefield from the nodes.Imagine a case where a node contains many fields, there will be plentyof 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 proceeeding // 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 begining 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; }} /* Druver 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); pairWiseSwap(&start); printf ( "n 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 proceeeding // 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 JaiswalC
// C# program to swap elements of// linked list by changing linksusing 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 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输入如下：
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 thefield from the nodes.Imagine a case where a node contains many fields, there will be plentyof 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 valueof 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* remaing = 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(remaing); // Return new head of modified list return newhead;} /* Function to add a node at the begining 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; }} /* Druver 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 << "nLinked list after calling pairWiseSwap() " ; printList(start); return 0;} // This is code is contributed by rathbhupendraC语言实现
/* This program swaps the nodes of linked list rather than swapping thefield from the nodes.Imagine a case where a node contains many fields, there will be plentyof 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* remaing = 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(remaing); // Return new head of modified list return newhead;} /* Function to add a node at the begining 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; }} /* Druver 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); // NOTE THIS CHANGE printf ( "n 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 remaing = 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(remaing); // 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( "" ); }}C
// C# program to swap elements// of linked list by changing linksusing 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 remaing = 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(remaing); // 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输入如下：
Linked list before calling pairWiseSwap() 1 2 3 4 5 6 7 Linked list after calling pairWiseSwap() 2 1 4 3 6 5 7如果发现任何不正确的中央, 或者想分享无关上述主题的更多信息, 请发表评论。
更多数据结构和算法相干内容请参考：lsbin - IT开发技术：https://www.lsbin.com/
查看以下更多算法相干的内容：
- 给定矩阵的所有行中的公共元素：https://www.lsbin.com/3695.html
- 如何计算两个数组中的最大求和门路？：https://www.lsbin.com/3689.html
- 算法题：将第一个元素加倍，而后将零挪动到结尾：https://www.lsbin.com/3542.html