Leetcode 24. Swap Nodes in Pairs(详细图解一看就会）

• 2020 年 8 月 24 日
• 筆記

题目内容

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.
大概意思是说每两个节点为一组交换位置。只使用常量空间，不能修改链表的值，只能修改链表的指针

解法（迭代）

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode *dummy = new ListNode(-1), *pre = dummy;
        dummy->next = head;
        while (pre->next && pre->next->next) {
            ListNode *t = pre->next->next;
            pre->next->next = t->next;
            t->next = pre->next;
            pre->next = t;
            pre = t->next;
        }
        return dummy->next;
    }
};

该代码已经是非常经典了，但乍一看还是有点晕，我们来对代码进行一步步的解析。

可以看出该代码实现了两个相邻节点的交换，最后并将pre指向了下一个节点，然后继续该过程

递归解法

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