# LeetCode24. Swap Nodes in Pairs（链表 / 模拟）

## LeetCode24. Swap Nodes in Pairs（链表）

• Medium
• Accepted：282,686
• Submissions：654,352

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.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

### 链接

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

### 题解

• 具体交换操作就是pre->next=node2 node2->next=node1 mode1->next=next，完成交换后，我们再让pre=node1更新信息。
• 时间复杂度$O(n)$。

### 代码

• Runtime: 4 ms, faster than 100.00% of C++ online submissions for Swap Nodes in Pairs.
• Memory Usage: 9 MB, less than 32.89% of C++ online submissions for Swap Nodes in Pairs.
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* virtualHead = new ListNode(0);
ListNode* pre = virtualHead;
while (pre->next && pre->next->next)
{
ListNode* node1 = pre->next;
ListNode* node2 = node1->next;
ListNode* next = node2->next;

// 交换
node2->next = node1;
node1->next = next;
pre->next = node2;

pre = node1; // 下一次交换
}
ListNode* retNode = virtualHead->next;
return retNode;
}
};
• Runtime: 3 ms, faster than 69.99% of C++ online submissions for Swap Nodes in Pairs.
• Memory Usage: 7.6 MB, less than 54.77% of C++ online submissions for Swap Nodes in Pairs.
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyNode = new ListNode(-1);

// 虚拟头节点
ListNode* cur = dummyNode;
while (cur->next != NULL && cur->next->next != NULL)
{
// 临时节点
ListNode* nextNode = cur->next;
ListNode* nextNextNode = cur->next->next->next;

// 注意，从第一个开始就已经更新了
cur->next = cur->next->next;
cur->next->next = nextNode;
cur->next->next->next= nextNextNode;

// 往后移动
cur = cur->next->next;
}

// 删除虚拟头结点