题目描述

题目链接：24. Swap Nodes in Pairs

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

例子

例子 1

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

例子 2

Input: head = []
Output: []

例子 3

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

Follow Up

Can you solve the problem without modifying the values in the list’s nodes? (i.e., Only nodes themselves may be changed.)

Constraints

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

解题思路

这道题的关键是搞清楚要交换的节点，以两个节点为一个单元进行调整，假设目前要调整的单元为： prev->A->B->next，其中 prev 及之前的调整已经完成，next 之后的调整还没开始。我们要做的是将其调整为 prev->B->A->next，再对 next 和 next->next 进行同样操作。而在这中间我们要进行的步骤是：

• 将 prev 指向 B (A 需要备份)，链表变成 prev->B->next->... , A->B->next->...
• 此时 A 之后的链表的顺序仍未被改变，将 A 指向 A->next->next （也就是 B->next）,此时链表变成 prev->B->next->..., A->next->...
• 将 prev->next (B) 指向 A，此时链表已经转换好，prev->B->A->next->...
• 将 A 设为 A->next, prev 设为 prev->next->next，接下来进行重复操作

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

        ListNode* new_head = head->next;
        ListNode* dummy = new ListNode();

        ListNode* curr = head;
        ListNode* prev = dummy;

        while (curr && curr->next) {
            prev->next = curr->next;
            curr->next = curr->next->next;
            prev->next->next = curr;
            curr = prev->next->next->next;
            prev = prev->next->next;
        }

        return new_head;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(1)

GitHub 代码同步地址： 24.SwapNodesInPairs.cpp

其他题目：
GitHub: Leetcode-C++-Solution
博客： Leetcode-Solutions