题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.

本题考虑到量个两种解法：第一种用循环的方法去解答，第二种用递归的方式去解答，但是递归在前面的介绍说过，递归并不是最好的解法，相反递归还可能存在递归栈溢出的问题，而且递归比循环更加的耗费资源。这里是记录一下若用递归的解答方式该怎解答。

循环方式解答，申请一个新的节点pre，将新的节点的next指向链表的开始部位。在使用一个tmp指针变量指向“需要交换的第一个节点”前面的节点。（第一组需要交换的节点的前一个节点当然是pre）
在使用start和end两个指针分别指向需要交换的第一个和第二个节点。
进行交换，将“本组需要交换的节点”的 前一个节点 的next指针指向“需要交换的第二个节点”
其次将 “本组需要交换的第一个节点”的next指针指向 “本组需要交换的第二个节点”的后面的那个节点
然后将 “本组需要交换的第二个节点”的next指针指向 "本组需要交换的第一个节点", 本次交换结束
最后将tmp的挪到下一组“需要交换的节点”的前一个节点，（即本次交换完成后的start节点）
当然交换过程可以用比较简洁的一行赋值语句进行，这里把他分开的原因是更清晰的展现交换的过程
时间复杂度 O(n), 空间复杂度 O(1)

代码如下：

# -*- coding: utf-8 -*-# @Author : xaohuihui# @Time : 19-12-12# @File : swap_pairs_linked.py# Software : study"""两两交换链表节点"""class ListNode: def __init__(self, x): self.val = x self.next = Nonedef swap_pairs(head: ListNode) -> ListNode: pre = ListNode(0) pre.next = head tmp = pre start = tmp.next # “需要交换的第一个节点” end = tmp.next.next # “需要交换的第二个节点” while tmp.next and tmp.next.next: tmp.next = end # “需要交换的第一个节点”的前面的一个节点，指向需要交换的第二个节点 start.next = end.next # “需要交换的第一个节点”指向“需要交换的第二个节点”的后面的节点 end.next = start # “需要交换的第二个节点”指向“需要交换的第一个节点” # 上面交换完毕，现在start节点处于第二个节点的位置， end节点在第一个节点的位置 tmp = start # 将tmp指向下一组“需要交换的第一个节点”的前面的一个节点， 即本次交换完成的第二个节点的位置 return pre.nextif __name__ == '__main__': node1 = ListNode(1) node2 = ListNode(2) node3 = ListNode(3) node4 = ListNode(4) node5 = ListNode(5) node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node5 result = swap_pairs(node1) while result: print(result.val) result = result.next

输出结果:

21435第二种解法 递归

递归解法，是将多组的交换抽象成一组交换，是先找到“本组需要交换的节点”的下一个节点
进行交换，“本组需要交换的第一个节点”的next指针指向“本组需要交换的第二个节点”的下一个节点
其次将“本组需要交换的第二个节点”的next指针指向 “本组需要交换的第一个节点”， 然后返回交换后的第一个节点（即交换前的第二个节点）

代码如下：

# -*- coding: utf-8 -*-# @Author : xaohuihui# @Time : 19-12-12# @File : swap_pairs_linked.py# Software : study"""两两交换链表节点"""class ListNode: def __init__(self, x): self.val = x self.next = Nonedef swap_pairs(head: ListNode) -> ListNode: if head is None or head.next is None: # 当长度为奇数时返回最后一个节点，当长度为偶数的时候返回None print(head.val if head else head) return head pre = head.next # head 为“第一个需要交换节点”， pre 为“第二个需要交换的节点” print(head.val, pre.val) head.next = swap_pairs(pre.next) # “第一个需要交换的节点” 指向 “第二个需要交换的节点”的后面的节点 pre.next = head # “第二个需要交换的节点” 指向 “第一个需要交换的节点” print("swap", head.val, pre.val, head.next.val if head.next else head.next) return preif __name__ == '__main__': node1 = ListNode(1) node2 = ListNode(2) node3 = ListNode(3) node4 = ListNode(4) node5 = ListNode(5) node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node5 result = swap_pairs(node1) while result: print(result.val) result = result.next

输出结果：

1 23 45swap 3 4 5swap 1 2 421435