两两交换链表节点，如何实现成长尾词？

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

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

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

解题思路：对于这道题，我们可以采用迭代的方法来解决。具体步骤如下：

1. 创建一个哑节点dummy，它的next指向链表的头节点head，这样方便处理头节点的情况。

2.创建一个指针cur指向哑节点dummy，它始终指向当前处理的节点的前一个节点。

3.遍历链表，每次找到一对相邻的节点，进行交换。

4.交换完成后，将cur指向当前处理的节点，继续下一轮交换。

5.遍历结束后，返回哑节点的next，即为交换后的链表的头节点。

下面是具体的代码实现：

python

class ListNode: def __init__(self, val=0, next=None): self.val=val self.next=next

def swapPairs(head): dummy=ListNode(0) dummy.next=head cur=dummy while cur.next and cur.next.next: a=cur.next b=a.next a.next=b.next b.next=a cur.next=b cur=a return dummy.next

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

示例 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