题目描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

样例

题解

该题为面试高频题

递归法

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) return head;

        ListNode* next = head->next;
        head->next = swapPairs(next->next);
        next->next = head;
        return next;
    }
};

非递归法

解法类似链表反转

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        auto dummy = new ListNode(0, head), p1 = dummy;

        while (p1->next && p1->next->next)
        {
            auto p2 = p1->next, p3 = p1->next->next;
            p1->next = p3;
            p2->next = p3->next;
            p3->next = p2;
            p1 = p2;
        }

        return dummy->next;
    }
};