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

给定一个链表，两两交换其中的相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例2：

输入：head = []
输出：[]

示例3：

输入：head = [1]
输出：[1]

提示：

• 链表中节点的数目在范围[0, 100]内

• 0 <= Node.val <= 100

思路

方法一：递归

通过递归的方式实现两两交换链表中的节点。
递归的终止条件是链表中没有节点或者链表中只有一个节点，此时无法进行交换。
如果链表中至少存在两个节点，则在两两交换链表中的节点之后，原始链表的头节点变成新链表的第二个节点，原始链表的第二个节点变成新链表的头节点。链表中的其余节点的两两交换可以通过递归实现。在对链表中的其余节点递归地两两交换之后，更新节点之间的指针关系，即可完成整个链表的两两交换。

用head表示原始链表的头节点，newhead表示新链表的头节点，原始链表的第二个节点，则原始链表的其余节点的头节点是newhead.next。令head.next=swapPairs(newhead.next)，表示将其余节点进行两两交换，交换后的新的头节点为head的下一个节点。然后令newhead.next=head，即完成了所有节点的交换。最后返回新的链表的头节点newhead。

class Solution:
	def swapPairs(self, head: ListNode)-> ListNode:
        if not head or not head.next:
            return head
        newhead = head.next
        head.next = self.swapPairs(newhead.next)
        newhead.next = head
        return newhead

复杂度分析

• 时间复杂度：$O(n)$，其中$n$是链表的节点数量。需要对每个节点进行更新指针的操作。
• 空间复杂度：$O(n)$，其中$n$是链表中的节点数量。空间复杂度主要取决于递归调用的栈空间。

方法二：迭代

通过迭代的方式实现两两交换链表中的节点。

class Solution:
	def swapPairs(self, head):
	dummyhead = ListNode(0)
	dummpyhead.next = head
	temp = dummpyhead
	while temp.next and temp.next.next:
        node1 = temp.next
        node2 = temp.next.next
        temp.next = node2
        node1.next = node2.next
        node2.next = node1
        temp = node1
   return dummpyhead.next

复杂度分析

• 时间复杂度： $O(n)$，其中$n$是链表的节点数量。需要对每个节点进行更新指针的操作。
• 空间复杂度： $O(1)$。

参考

官方题解(动图好评)