24. 两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
这道题目正常模拟就可以了。
建议使用虚拟头结点，这样会方便很多，要不然每次针对头结点（没有前一个指针指向头结点），还要单独处理。
接下来就是交换相邻两个元素了，此时一定要画图，不画图，操作多个指针很容易乱，而且要操作的先后顺序
初始时，cur指向虚拟头结点，然后进行如下三步：
操作之后，链表如下：
看这个可能就更直观一些了：
对应的C++代码实现如下： （注释中详细和如上图中的三步做对应）
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
ListNode* cur = dummyHead;
while(cur->next != nullptr && cur->next->next != nullptr) {
ListNode* tmp = cur->next; // 记录临时节点
ListNode* tmp1 = cur->next->next->next; // 记录临时节点
cur->next = cur->next->next; // 步骤一
cur->next->next = tmp; // 步骤二
cur->next->next->next = tmp1; // 步骤三
cur = cur->next->next; // cur移动两位，准备下一轮交换
}
return dummyHead->next;
}
};- 时间复杂度：O(n)
- 空间复杂度：O(1)
拓展
这里还是说一下，大家不必太在意力扣上执行用时，打败多少多少用户，这个统计不准确的。
做题的时候自己能分析出来时间复杂度就可以了，至于力扣上执行用时，大概看一下就行。
上面的代码我第一次提交执行用时8ms，打败6.5%的用户，差点吓到我了。
心想应该没有更好的方法了吧，也就$O(n)$的时间复杂度，重复提交几次，这样了：
力扣上的统计如果两份代码是 100ms 和 300ms的耗时，其实是需要注意的。
如果一个是 4ms 一个是 12ms，看上去好像是一个打败了80%，一个打败了20%，其实是没有差别的。 只不过是力扣上统计的误差而已。
其他语言版本
C:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
//递归版本
struct ListNode* swapPairs(struct ListNode* head){
//递归结束条件：头节点不存在或头节点的下一个节点不存在。此时不需要交换，直接返回head
if(!head || !head->next)
return head;
//创建一个节点指针类型保存头结点下一个节点
struct ListNode *newHead = head->next;
//更改头结点+2位节点后的值，并将头结点的next指针指向这个更改过的list
head->next = swapPairs(newHead->next);
//将新的头结点的next指针指向老的头节点
newHead->next = head;
return newHead;
}//迭代版本
struct ListNode* swapPairs(struct ListNode* head){
//使用双指针避免使用中间变量
typedef struct ListNode ListNode;
ListNode *fakehead = (ListNode *)malloc(sizeof(ListNode));
fakehead->next = head;
ListNode* right = fakehead->next;
ListNode* left = fakehead;
while(left && right && right->next ){
left->next = right->next;
right->next = left->next->next;
left->next->next = right;
left = right;
right = left->next;
}
return fakehead->next;
}Java：
// 递归版本
class Solution {
public ListNode swapPairs(ListNode head) {
// base case 退出提交
if(head == null || head.next == null) return head;
// 获取当前节点的下一个节点
ListNode next = head.next;
// 进行递归
ListNode newNode = swapPairs(next.next);
// 这里进行交换
next.next = head;
head.next = newNode;
return next;
}
} class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dumyhead = new ListNode(-1); // 设置一个虚拟头结点
dumyhead.next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
ListNode cur = dumyhead;
ListNode temp; // 临时节点，保存两个节点后面的节点
ListNode firstnode; // 临时节点，保存两个节点之中的第一个节点
ListNode secondnode; // 临时节点，保存两个节点之中的第二个节点
while (cur.next != null && cur.next.next != null) {
temp = cur.next.next.next;
firstnode = cur.next;
secondnode = cur.next.next;
cur.next = secondnode; // 步骤一
secondnode.next = firstnode; // 步骤二
firstnode.next = temp; // 步骤三
cur = firstnode; // cur移动，准备下一轮交换
}
return dumyhead.next;
}
}Python：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
res = ListNode(next=head)
pre = res
# 必须有pre的下一个和下下个才能交换，否则说明已经交换结束了
while pre.next and pre.next.next:
cur = pre.next
post = pre.next.next
# pre，cur，post对应最左，中间的，最右边的节点
cur.next = post.next
post.next = cur
pre.next = post
pre = pre.next.next
return res.next
