当前位置：首页 > article >正文

每日一题——两两交换链表中的节点

article 2025/3/13 6:51:33

以下是整理成详细CSDN文档的格式，用于解释如何两两交换链表中的节点：

两两交换链表中的节点

- 题目描述
- 示例
- - 示例 1
  - 示例 2
  - 示例 3
- 提示
- 初始思路
- 代码实现
- 参考官方教程思路
- 总结

题目描述

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

示例

示例 1

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2

输入：head = []
输出：[]

示例 3

输入：head = [1]
输出：[1]

提示

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

初始思路

对于这个问题，我们可以通过迭代的方式进行节点交换。首先检查当前节点和下一个节点是否存在，如果存在，则交换这两个节点。然后继续检查下一个节点对，直到链表结束。

代码实现

以下是使用C语言实现的代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* swapPairs(struct ListNode* head) {
    // 如果链表为空或者只有一个节点，不需要交换，直接返回头节点
    if (head == NULL || head->next == NULL) {
        return head;
    }
    
    // 初始化first指针指向第一个节点，second指针指向第二个节点
    struct ListNode* first = head;
    struct ListNode* second = head->next;
    
    // third指针指向第二个节点的下一个节点，即下一个待交换的节点对中的第一个节点
    struct ListNode* third = head->next->next;
    
    // 交换first和second节点：将first的next指向third，second的next指向first，然后更新头节点为second
    first->next = third;
    second->next = first;
    head = second;

    // 初始化current指针，用于遍历链表，寻找需要交换的节点对
    struct ListNode* current = first;
    
    // 遍历链表，交换节点对
    while (current->next != NULL && current->next->next != NULL) {
        // 定位到下一个需要交换的节点对
        first = current->next;
        second = current->next->next;
        third = second->next; // third指向second的下一个节点
        
        // 执行节点交换：将current的next指向second，first的next指向third，second的next指向first
        current->next = second;
        first->next = third;
        second->next = first;
        
        // 移动current指针到下一个节点对的第一个节点，继续循环
        current = first;
    }
    
    // 返回交换后的链表头节点
    return head;
}

参考官方教程思路

为了简化问题，我们可以使用一个虚拟头节点（dummy head），这样可以使边界情况的处理更加简单。以下是使用C语言实现的代码：

#include <stdlib.h> // 引入stdlib.h头文件以使用malloc函数

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* swapPairs(struct ListNode* head) {
    // 创建一个虚拟头节点dummyHead，其next指向实际的头节点head
    // 使用虚拟头节点可以简化对头节点交换的处理
    struct ListNode* dummyHead = malloc(sizeof(struct ListNode)); // 动态分配内存
    dummyHead->next = head; // 将虚拟头节点的next指向实际的头节点
    struct ListNode* temp = dummyHead; // 使用temp指针遍历链表

    // 遍历链表，寻找需要交换的节点对
    while (temp->next != NULL && temp->next->next != NULL) {
        // first指向当前节点对的第一个节点
        struct ListNode* first = temp->next;
        // second指向当前节点对的第二个节点
        struct ListNode* second = temp->next->next;
        
        // 交换节点对的步骤：
        // 1. 将temp的next指向second，即当前节点对的第二个节点
        temp->next = second;
        // 2. 将first的next指向second的next，即跳过second，指向下一个节点对的第一个节点
        first->next = second->next;
        // 3. 将second的next指向first，完成两个节点的交换
        second->next = first;
        
        // 将temp向前移动到下一个节点对的第一个节点，继续循环
        temp = first;
    }
    
    // 返回虚拟头节点的下一个节点，即交换后的链表头节点
    // 由于dummyHead是一个虚拟节点，不包含在最终的链表中，所以返回dummyHead->next
    return dummyHead->next;
}