【力扣】24. 两两交换链表中的节点

24. 两两交换链表中的节点

题目描述

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

示例 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 (NULL == head || NULL == head->next) {
        return head;
    }

    // 定义临时节点保存头节点的下一个节点
    struct ListNode* ptr = head->next;
    // 头节点下一个节点指向剩余链表
    head->next = swapPairs(ptr->next);
    // 临时节点成为新的头节点指向旧的头节点
    ptr->next = head;
    // 返回新的头节点
    return ptr;
}

复杂度分析
时间复杂度为 O(n)，其中 n 是链表的节点数量。
空间复杂度为 O(n)，其中 n 是链表的节点数量。

迭代

• C 语言

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

    if (NULL == head) {
        return head;
    }

    // 定义哑节点
    struct ListNode* dummyHead =
        (struct ListNode*)malloc(sizeof(struct ListNode));
    dummyHead->next = head;

    // 定义临时节点
    struct ListNode* temp = dummyHead;
    while (NULL != temp->next && NULL != temp->next->next) {
        struct ListNode* ptr1 = temp->next;
        struct ListNode* ptr2 = ptr1->next;

        // 交换
        temp->next = ptr2;
        ptr1->next = ptr2->next;
        ptr2->next = ptr1;
        temp = ptr1;
    }
    return dummyHead->next;
}

复杂度分析
时间复杂度为 O(n)，其中 n 是链表的节点数量。
空间复杂度为 O(1)。