通过只调整链(而不是数据)来交换两个相邻的元素,分别使用a)单 链表;b)双向表链。 用C++实现并给出具体的实现例子
时间: 2024-09-20 17:09:10 浏览: 36
a) 在单链表中交换两个相邻节点:
```cpp
// 定义链表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
// 函数用于交换单链表中相邻的两个节点
void swapAdjacentNodes(ListNode*& head) {
if (head == nullptr || head->next == nullptr)
return; // 如果链表为空或只有一个节点,无需交换
ListNode* current = head;
ListNode* temp = nullptr;
// 找到第二个节点,并保存下一个节点的指针
while (current != nullptr && current->next != nullptr) {
temp = current->next;
current->next = temp->next; // 将当前节点的下一个指向第三个节点
temp->next = current; // 将第二个节点的下一个指向前一个节点
current = temp; // 移动当前指针到第二个节点
}
}
// 使用示例
ListNode* list = new ListNode(1); // 创建链表: 1 -> NULL
list->next = new ListNode(2); // 1 -> 2 -> NULL
swapAdjacentNodes(list); // 交换后: 2 -> 1 -> NULL
```
b) 在双向链表中交换两个相邻节点:
```cpp
// 定义双向链表节点结构体
struct DoublyListNode {
int val;
DoublyListNode* prev;
DoublyListNode* next;
DoublyListNode(int x) : val(x), prev(nullptr), next(nullptr) {}
};
// 函数用于交换双向链表中相邻的两个节点
void swapAdjacentNodes(DoublyListNode*& head) {
if (head == nullptr || head->prev == nullptr || head->next == nullptr)
return;
DoublyListNode* current = head;
DoublyListNode* temp = nullptr;
// 找到第二个节点,并保存前驱和后继的指针
temp = current->prev;
current->prev->next = current->next;
current->next->prev = current->prev;
current->prev = temp;
current->next = temp->next;
temp->next = current;
}
// 使用示例
DoublyListNode* dblList = new DoublyListNode(1); // 创建链表: 1 <-> NULL <-> NULL
dblList->prev = nullptr; // 添加前驱指针
dblList->next = new DoublyListNode(2); // 1 <-> 2 <-> NULL
swapAdjacentNodes(dblList); // 交换后: 2 <-> 1 <-> NULL
```
阅读全文