给定一个链表和其中的两个键，交换两个给定键的节点。应通过更改链接来交换节点。当数据包含许多字段时，在许多情况下交换节点的数据可能会很昂贵。
可以假设链表中的所有键都是不同的。
例子：
输入： 10->15->12->13->20->14，x = 12，y = 20 输出： 10->15->20->13->12->14 输入： 10->15->12->13->20->14，x = 10，y = 20 输出： 20->15->12->13->10->14 输入： 10->15->12->13->20->14，x = 12，y = 13 输出： 10->15->13->12->20->14
这可能看起来是一个简单的问题，但这是一个有趣的问题，因为它有以下情况需要处理。
- x 和 y 可能相邻也可能不相邻。
- x 或 y 都可以是头节点。
- x 或 y 可能是最后一个节点。
- x 和/或 y 可能不存在于链表中。
如何编写一个干净的工作代码来处理上述所有可能性。
这个想法是首先在给定的链表中搜索 x 和 y。如果其中任何一个不存在，则返回。在搜索 x 和 y 时，跟踪当前和以前的指针。首先更改前一个指针的下一个，然后更改当前指针的下一个。
下面是上述方法的实现。
class Node { public: int data; Node* next; }; void swapNodes(Node** head_ref, int x, int y) { if (x == y) return; Node *prevX = NULL, *currX = *head_ref; while (currX && currX->data != x) { prevX = currX; currX = currX->next; } Node *prevY = NULL, *currY = *head_ref; while (currY && currY->data != y) { prevY = currY; currY = currY->next; } if (currX == NULL || currY == NULL) return; if (prevX != NULL) prevX->next = currY; else *head_ref = currY; if (prevY != NULL) prevY->next = currX; else *head_ref = currX; Node* temp = currY->next; currY->next = currX->next; currX->next = temp; } void push(Node** head_ref, int new_data) { Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void printList(Node* node) { while (node != NULL) { cout << node->data << " "; node = node->next; } } int main() { Node* start = NULL; 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 swapNodes() "; printList(start); swapNodes(&start, 4, 3); cout << "\nLinked list after calling swapNodes() "; printList(start); return 0; }
优化： 可以优化上面的代码以在单次遍历中搜索 x 和 y。两个循环用于保持程序简单。
更简单的方法——
#include <iostream> using namespace std; class Node { public: int data; class Node* next; Node(int val, Node* next) : data(val) , next(next) { } void printList() { Node* node = this; while (node != NULL) { cout << node->data << " "; node = node->next; } cout << endl; } }; void push(Node** head_ref, int new_data) { (*head_ref) = new Node(new_data, *head_ref); } void swap(Node*& a, Node*& b) { Node* temp = a; a = b; b = temp; } void swapNodes(Node** head_ref, int x, int y) { if (x == y) return; Node **a = NULL, **b = NULL; while (*head_ref) { if ((*head_ref)->data == x) { a = head_ref; } else if ((*head_ref)->data == y) { b = head_ref; } head_ref = &((*head_ref)->next); } if (a && b) { swap(*a, *b); swap(((*a)->next), ((*b)->next)); } } int main() { Node* start = NULL; 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 swapNodes() "; start->printList(); swapNodes(&start, 6, 1); cout << "Linked list after calling swapNodes() "; start->printList(); }
输出
Linked list before calling swapNodes() 1 2 3 4 5 6 7 Linked list after calling swapNodes() 6 2 3 4 5 1 7
