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

自己的做法

算法思想

先添加一个哨兵节点sentinel，初始时 指针node指向哨兵节点。判断哨兵节点后是否有两个节点。

如果有，则使用first和second指针指向这两个节点，首先：

• node节点的next指向second
• first节点的next指向second节点的next
• second节点的next指向first

两个节点交换完毕。

然后node指向当前节点的下下个节点。

算法实现

class Solution {
public:
    static ListNode* swapPairs(ListNode* head) {
        ListNode * sentinel = new ListNode();
        sentinel->next = head;
        ListNode * node = sentinel;
        while (node->next != nullptr && node->next->next != nullptr) {
            ListNode * first = node->next;
            ListNode * second = node->next->next;
            
            node->next = second;
            first->next = second->next;
            second->next = first;

            node = node->next->next;
        }
        return sentinel->next;
    }
};

性能分析

时间复杂度：$O(N)$。

空间复杂度：$O(1)$。

参考解法有两种解法。

第一种，使用递归，时间复杂度和空间复杂度都是$O(n)$。

第二种和我的方法一样。