极客笔记C++程序 在不交换数据的情况下交换链表中的节点
在C++中，链表是一种非常重要的数据结构，而涉及到链表中元素交换的问题是一个非常常见的问题。但是传统的交换节点数据的方法有时候并不能满足实际应用需求，因此我们有必要探讨一下在不交换数据的情况下如何交换链表中的节点。
什么是链表？
链表是一种非常常见的用来储存线性数据结构的数据卡片。与传统的数组不同，链表允许我们在内存中任意添加或删除元素，这是我们日常开发中经常需要用到的一个特性。
链表是由一个个节点构成的，每个节点都有一个值和一个指向下一个节点的指针。
下面是一个简单的C++结构体定义来描述链表节点：
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
简单来说，这个结构体表示了一个节点，其中val表示节点的值，next表示指向下一个节点的指针。如果next为NULL，则说明这是链表的尾节点。
传统的链表节点交换方法
首先让我们来看一下传统的链表节点交换方法。这种方式是通过交换节点的值来达到节点交换的目的。
例如，我们有一个长度为4的链表，其值为1->2->3->4。如果我们想要将第2个和第3个节点进行交换，那么我们可以这样做：
void swapNodes(ListNode* head, int n1, int n2) {
// 找到待交换的节点
ListNode *node1 = head, *node2 = head;
while (n1 > 1) {
node1 = node1->next;
n1--;
}
while (n2 > 1) {
node2 = node2->next;
n2--;
}
// 交换两个节点的值
int tmp = node1->val;
node1->val = node2->val;
node2->val = tmp;
}
这个函数会找到第n1个节点和第n2个节点，然后交换它们的值。例如，如果我们想要交换第2个和第3个节点，那么n1=2，n2=3。
虽然这种方法很简单实用，但是它存在一些问题：
- 如果我们的节点是一个复杂的结构体，而不仅仅是一个简单的int类型，那么交换节点的值可能会带来更多的开销。
- 如果我们的链表很长，那么交换节点值的时间复杂度可能会非常高。
因此，我们需要一种更高效的方法来交换链表节点。
不交换数据的情况下交换链表节点
我们来看一下不交换数据的情况下如何交换链表中的节点。
首先让我们来考虑一种比较暴力的方法：我们可以将第n1个节点从链表中删除，再将它插入到第n2个节点的后面。这个方法并不需要交换节点的数据，而是仅仅需要修改链表的指针。具体实现如下：
ListNode* swapNodes(ListNode* head, int n1, int n2) {
if (n1 == n2) return head;
// 找到待交换的节点
ListNode *node1 = head, *node2 = head;
ListNode *prev1 = NULL, *prev2 = NULL;
while (n1 > 1) {
prev1 = node1;
node1 = node1->next;
n1--;
}
while (n2 > 1) {
prev2 = node2;
node2 = node2->next;
n2--;
}
// 如果n1 > n2，则交换一下node1和node2，确保node1是在node2前面
if (n1 > n2) {
swap(node1, node2);
swap(prev1, prev2);
}
// 如果node1是头结点，则修改head指针；否则将prev1->next指向node2
if (prev1 == NULL) {
head = node2;
} else {
prev1->next = node2;
}
// 将node1插入到node2的前面
ListNode *tmp = node2->next;
node2->next = node1->next;
node1->next = tmp;
// 如果node1是头结点，则直接返回node2；否则返回head
return (prev1 == NULL ? node2 : head);
}
这个函数会找到第n1个节点和第n2个节点。如果n1 > n2，则交换一下node1和node2，可以确保node1是在node2前面。然后，我们将node1从链表中删除，并将它插入到node2的前面。
这种方法在时间复杂度上比交换节点值的方法更加优秀。事实上，在最坏情况下，它只需要遍历链表两次。
示例代码
下面是一个完整的示例代码，实现了交换链表节点的功能：
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* swapNodes(ListNode* head, int n1, int n2) {
if (n1 == n2) return head;
// 找到待交换的节点
ListNode *node1 = head, *node2 = head;
ListNode *prev1 = NULL, *prev2 = NULL;
while (n1 > 1) {
prev1 = node1;
node1 = node1->next;
n1--;
}
while (n2 > 1) {
prev2 = node2;
node2 = node2->next;
n2--;
}
// 如果n1 > n2，则交换一下node1和node2，确保node1是在node2前面
if (n1 > n2) {
swap(node1, node2);
swap(prev1, prev2);
}
// 如果node1是头结点，则修改head指针；否则将prev1->next指向node2
if (prev1 == NULL) {
head = node2;
} else {
prev1->next = node2;
}
// 将node1插入到node2的前面
ListNode *tmp = node2->next;
node2->next = node1->next;
node1->next = tmp;
// 如果node1是头结点，则直接返回node2；否则返回head
return (prev1 == NULL ? node2 : head);
}
void printList(ListNode* head) {
while (head != NULL) {
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
int main() {
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
printList(head);
head = swapNodes(head, 2, 3);
printList(head);
return 0;
}
结论
在C++中，链表是一种非常重要的数据结构，节点交换是链表操作中的常见问题之一。传统的节点交换方法需要交换节点的数据，可能会带来额外的开销，因此我们可以考虑使用不交换数据的方法来交换链表节点。具体来说，我们可以将要交换的节点从链表中删除，并将它插入到另一个节点的前面。这种方法在时间复杂度上更加优秀，可以在最坏情况下只需要遍历链表两次。