给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。用C语言完整实现一下
时间: 2024-11-23 11:39:39 浏览: 24
在C语言中,我们可以使用迭代的方式来解决这个问题,创建一个新的链表结构作为结果,并通过遍历原始链表来进行相邻节点的交换。以下是一个完整的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
// 创建新链表节点
ListNode* createNode(int val) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->val = val;
newNode->next = NULL;
return newNode;
}
// 交换相邻节点
ListNode* swapNodes(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode* dummyHead = createNode(0); // 创建虚拟头节点
dummyHead->next = head;
ListNode* prev = dummyHead;
ListNode* curr = head->next;
ListNode* next = curr->next;
while (curr != NULL && next != NULL) {
// 交换相邻节点
curr->next = next->next;
next->next = curr;
prev->next = next; // 更新prev指向当前节点
prev = curr; // 移动prev到curr
curr = curr->next; // 移动curr到下一个节点
if (curr != NULL) {
next = curr->next;
}
}
return dummyHead->next; // 返回交换后的新头节点
}
// 打印链表
void printList(ListNode* node) {
while (node != NULL) {
printf("%d -> ", node->val);
node = node->next;
}
printf("NULL\n");
}
int main() {
// 测试示例:1->2->3->4->5
ListNode* head = createNode(1);
head->next = createNode(2);
head->next->next = createNode(3);
head->next->next->next = createNode(4);
head->next->next->next->next = createNode(5);
printf("Original List:\n");
printList(head);
head = swapNodes(head);
printf("After swapping nodes:\n");
printList(head);
return 0;
}
```
这个程序首先检查是否为特殊情况进行处理(空链表或只有一个节点),然后创建一个虚拟头节点以方便处理边界条件。接着,我们使用三个指针`prev`, `curr`, 和 `next` 来遍历并依次交换相邻节点。最后,返回虚拟头节点之后的实际头节点,完成了链表的交换。
阅读全文