24. 两两交换链表中的节点-一一网

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

输入：head = [1,2,3,4]
输出：[2,1,4,3]
复制代码

解法一

迭代自己看答案前的做法。主要思想是：依次取出两个节点node1, node2，交换过后让node1的next指向node2的子节点，最后整体拼接在目标链表后面。

def swapPairs1(head):

    # 特殊判断
    if head is None: return None
    if head.next is None: return head

    dummy = point = ListNode()  # 声明头结点和构建链表的节点

    def swapTwoNodes(node1, node2, point):
        """交换两个节点位置，并拼接在结果链表后面"""
        n2_next = node2.next
        point.next = node2
        node2.next = node1
        node1.next = n2_next  # 将交换后的node1的next指向 node2的子节点

    while head is not None:
        if head.next:  # 如果 head.next 不为空，就交换 head 和 head.next
            if point.next is not None:  # 如果 point.next 不为空，就将节点指向下下级节点，用于拼接后面交换的节点
                point = point.next.next
            swapTwoNodes(head, head.next, point)
            head = head.next  # 运行代码走一下就知道，head.next就是还没有被交换过的节点
        else:
            head = head.next  # 如果head.next为空，就直接指向next

    return dummy.next
复制代码

官方的写法：

def swapPairs2(head):
    """迭代，官方写法"""
    dummyHead = ListNode()
    dummyHead.next = head  # 创建哑节点，并指向head
    temp = dummyHead  # 每次需要交换 temp 后面的两个节点
    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  # temp 指向交换过后 node1 的位置
    return dummyHead.next
复制代码

复杂度分析

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

解法二

参考力扣官方答案。主要思路：可以通过递归的方式实现两两交换链表中的节点。
递归的终止条件是链表中没有节点，或者链表中只有一个节点，此时无法进行交换。

def swapPairs3(head):
    """递归"""
    if not head or not head.next: return head  # 特殊值判断
    newhead = head.next  # 记录头结点的下一个节点
    head.next = swapPairs2(newhead.next)  # 将后面节点newhead.next的交换结果，作为head的next节点
    newhead.next = head  # 交换节点，将head作为newhead的next节点
    return newhead
复制代码