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

原题链接: 24. 两两交换链表中的节点 - 力扣（Leetcode）

tag: 链表.

一. 题目

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

二. 题解

本题采用 三指针 的解法, 前指针 prev , 中指针 first , 后指针 second .

交换节点前.

ListNode* dummy = new ListNode(0, head), * prev = dummy;

当 prev 指针指向的前驱结点的后两个节点不为空时, 循环迭代.

prev->next != nullptr && prev->next->next != nullptr;

定义中指针 first, 后指针 second .

ListNode* first = prev->next, * second = first->next;

改变第一个节点的 next 指针指向.

first->next = second->next;

改变第二个节点的 next 指针指向.

second->next = first;

改变前驱节点的 next 指针指向.

prev->next = second;

更新 prev 指针.

prev = first;

重复上述步骤.

prev->next == nullptr; 循环终止.

返回链表的头节点.

head = dummy->next;

delete dummy;

return head;

三. 复杂度分析

时间复杂度: O(N), 其中 N 表示链表的结点个数.

空间复杂度: O(1).

四. 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(0, head), * prev = dummy;    // 定义虚拟头节点 dummy, 前指针 prev
        while (prev->next && prev->next->next) {
            ListNode* first = prev->next, * second = first->next;    // 定义中指针 first, 后指针 second
            first->next = second->next;    // 改变第一个节点的 next 指针指向
            second->next = first;    // 改变第二个节点的 next 指针指向
            prev->next = second;    // 改变前驱节点的 next 指针指向 
            prev = first;    // 更新 prev 指针
        }
        head = dummy->next;    // 返回链表的头节点
        delete dummy;  
        return head;
    }
};