LeetCode 24. 两两交换链表中的节点

本题中，要求实际的进行节点交换，不仅仅是单纯的改变节点内部的值。

在这里，其实有递归跟非递归两种思路，但是核心思想类似，都是要交换相邻节点的链表形态完成整个链表的调整。

思路一：递归

使用递归时，需要明确终止条件，其次，对于完整的调用栈先不要急于下手，这样一层层下来，很容易无从下手。递归，主要是不断重复相同的事情，但遇到终止条件时会层层返回。在这种情形下，可以考虑先关注一层调用单元的情况。

在这里，我们首先要明确的是：终止的条件，返回内容 ，以及当前层调用单元具体做了什么。

接着看本题：

• 终止条件：就是 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