24. Swap Nodes in Pairs


Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

Example 1:

**Input:** head = [1,2,3,4]
**Output:** [2,1,4,3]

Example 2:

**Input:** head = []
**Output:** []

Example 3:

**Input:** head = [1]
**Output:** [1]

Constraints:

  • The number of nodes in the list is in the range [0, 100].
  • 0 <= Node.val <= 100

这道题不算难,是基本的链表操作题,我们可以分别用递归和迭代来实现。对于迭代实现,还是需要建立 dummy 节点,注意在连接节点的时候,最好画个图,以免把自己搞晕了,参见代码如下:

解法一:

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;
    }
};

递归的写法就更简洁了,实际上利用了回溯的思想,递归遍历到链表末尾,然后先交换末尾两个,然后依次往前交换:

解法二:

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;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/24

类似题目:

Reverse Nodes in k-Group

Swapping Nodes in a Linked List

参考资料:

https://leetcode.com/problems/swap-nodes-in-pairs

https://leetcode.com/problems/swap-nodes-in-pairs/discuss/11030/My-accepted-java-code.-used-recursion.

LeetCode All in One 题目讲解汇总(持续更新中…)

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,快快加入吧~)

知识星球 喜欢请点赞,疼爱请打赏❤️.

微信打赏

|

Venmo 打赏


—|—


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation