如何实现力扣两两交换链表节点的算法？

本文共计832个文字，预计阅读时间需要4分钟。

题目：给定一个链表，两两交换相邻节点，并返回交换后链表的头节点。（即，只能进行节点交换，不能修改节点内部的值）

示例 1：输入：链表 1->2->3->4输出：4->2->3->1

解题思路：对于这道题，我们可以使用递归的方法来解决。递归的基本思路是：先递归地交换当前节点和下一个节点的值，然后递归地处理下一个节点和下下个节点，直到链表末尾。

具体步骤如下：

1.如果当前节点是最后一个节点或下一个节点不存在，直接返回当前节点。

2.递归地交换当前节点和下一个节点的值。

3.将当前节点指向递归调用交换后的下一个节点。

4.返回当前节点。

题目：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）

示例 1：

解题思路
对于这道题我们可以为原链表增加一个哨兵卫，然后创建三个指针，最前面的指针用于判断是否还存在需要交换的节点，后面的两个节点用于交换两个节点。

图解：

下面创建三个指针，pre，node1，node2。

第一步：我们运用指针让node1指向的节点的next变为node2指向节点的next（这一步是为了链接好整个链表）

第二步：我们让node2的next指向node1

此时的链表图就变成了：

下面我们再让pre直接赋值为node1，开始下面两个节点的交换。

既然我们要让原链表的所有元素最后都会两两交换，那肯定是要使用循环的但是循环的条件要怎么去判断呢？我们要使用哪一个指针作为循环的判断条件呢？这里我们就使用pre指针当pre指针的next和pre指针next的next都还存在值而不是NULL那，证明原链表的后面还有至少两个元素这两个元素是可以交换的。

下面是c代码的实现

struct ListNode* swapPairs(struct ListNode* head) { //方法使用三指针迭代，我们额外将一个哨兵卫将其链接给给予我们的链表 //然后我们只用改变这个哨兵卫的后两个指针指向即可，最后再将指向哨兵卫的这个指针指向下一个相当于哨兵卫节点功能的节点 struct ListNode* tmp = (struct ListNode*)malloc(sizeof(struct ListNode)); tmp->next = head; struct ListNode* newhead = tmp; while (tmp->next && tmp->next->next)//当tmp的后面两个节点都不为空时表示我已交换下面的两个节点 { struct ListNode* node1 = tmp->next; struct ListNode* node2 = node1->next; tmp->next = node2; node1->next = node2->next; node2->next = node1; tmp = node1; } return newhead->next;//这里的newhead指向的我们创建的那个哨兵卫，哨兵卫的next才是指向交换元素后链表的第一个节点 }//最简单的方法时间复杂度o(n)空间复杂度o（1 blog.51cto.com/u_15838996/6273817