24. 两两交换链表中的节点
题目来源：https://leetcode-cn.com/problems/swap-nodes-in-pairs
题目
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
解题思路
本题中，要求实际的进行节点交换，不仅仅是单纯的改变节点内部的值。
在这里，其实有递归跟非递归两种思路，但是核心思想类似，都是要交换相邻节点的链表形态完成整个链表的调整。
思路一：递归
使用递归时，需要明确终止条件，其次，对于完整的调用栈先不要急于下手，这样一层层下来，很容易无从下手。递归，主要是不断重复相同的事情，但遇到终止条件时会层层返回。在这种情形下，可以考虑先关注一层调用单元的情况。
在这里，我们首先要明确的是：终止的条件，返回内容 ，以及当前层调用单元具体做了什么。
接着看本题：
- 终止条件：就是 head 为空，或者 head.next 为空。这表示链表没有节点，或者只有一个节点，这样将无法交换，也就是终止条件。
- 返回内容：返回的是交换完成的子链表。
- 调用单元：在这里 ，设前后节点 front_node, tail_node，对两个节点进行交换，front_node 连接后面交换完成的子链表，tail_node 连接 front_node。
这就是递归的思路。
思路二：非递归
非递归跟递归的思路其实是相类似的。
设前后节点 front_node 和 tail_node，核心同样是交换前后节点，但是要增加辅助节点 pre，记录 front_node 的前节点。
具体算法：
- 定义前后节点 front_node，tail_node；
- 交换前后节点；
- 更新 pre.next 指向交换后的头；
- 循环结束，返回最后的交换结果。
具体的代码实现如下。
代码实现
递归
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
# 如果链表为空，或者只有一个节点，直接返回 head
if not head or not head.next:
return head
# 需交换的前后节点
front_node = head
tail_node = head.next
# 交换节点
front_node.next = self.swapPairs(tail_node.next)
tail_node.next = front_node
return tail_node
非递归
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
# dummy 简化边界条件
dummy = ListNode(-1)
dummy.next = head
pre = dummy
while head and head.next:
front_node = head
tail_node = head.next
# 交换
pre.next = tail_node
front_node.next = tail_node.next
tail_node.next = front_node
# 重置 pre, head
pre = front_node
head = front_node.next
return dummy.next
实现结果
递归结果：
实现结果|递归
非递归结果：
实现结果|非递归
以上就是使用递归和非递归的思路，对链表相邻节点进行交换，解决《两两交换链表中的节点》问题的主要内容。
欢迎关注微信公众号《书所集录》
