题目要求
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。


解题思路
首先,定义一个虚拟头结点(哨兵节点),其 next 指向原链表头。这有助于处理头节点交换时的边界情况。
我们需要考虑剩余节点的奇偶性:
- 偶数节点:所有节点均可成对交换。
- 奇数节点:最后一个节点无需交换。
在单链表中,为了交换两个相邻节点(设为 A 和 B),我们需要一个指针 right 指向它们的前驱节点。如果 right 指向 A,则无法回溯到前驱连接新的头节点。因此,right 应始终指向待交换对的前一个节点。
交换完成后,right 需要向后移动两位,以便操作下一对节点(例如从 A、B 移动到 C、D)。
终止条件
- 奇数情况:当
right->next->next == NULL时停止,因为最后一个节点不需要交换。 - 偶数情况:当
right->next == NULL时停止。
指针操作细节
由于交换会改变 next 指针,导致部分节点地址丢失,需使用临时指针保存:
current保存第一个节点(A)。current1保存第三个节点(C),即下一对的起始位置。
交换步骤:
right->next指向第二个节点(B)。right->next->next指向第一个节点(A)。current->next指向current1。right更新为right->next->next(即新的 B 节点位置)。
完整代码
#include<stdio.h>
#include<stdlib.h>
struct Node{
int data;
* ;
};
Node* {
( Node*)(( Node));
(newNode == ){
();
;
}
newNode->data = data;
newNode->next = ;
newNode;
}
{
(head == ){
();
} {
(head != ){
(, head->data);
head = head->next;
}
();
}
}
{
*head;
(right->next != && right->next->next != ){
right->next;
right->next->next->next;
right->next = right->next->next;
right->next->next = current;
current->next = current1;
right = right->next->next;
}
}
{
createNode();
head->next = createNode();
head->next->next = createNode();
head->next->next->next = createNode();
head->next->next->next->next = createNode();
printList(head);
changeNode(&head);
();
printList(head);
;
}


