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

定义链表

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

解法一

循环遍历，a 为当前节点，b 为 a 的 next 节点，将 a 的 next 指针设置为 b 的 next 指针，将 b 的 next 指针设置为 a，并将前一节点 pre 的 next 指针设置为 b，从而完成 a 和 b 的交换，再将前一节点设置为 a，继续遍历，直到 a 或 b 不存在，需要注意，这里将输入增加一个前置节点 pre，方便通过 pre.next 来返回调整后的链表 head。

如下图所示，实线为原指针，虚线为调整后的指针（由 1, 2 开始）：0

def swap_pairs(head):
    pre, pre.next = ListNode(0), head
    tmp = pre
    while tmp.next and tmp.next.next:
        a, b = tmp.next, tmp.next.next
        tmp.next = b
        a.next = b.next
        b.next = a
        tmp = a
    return pre.next

执行用时 :76 ms
内存消耗 :13.7 MB

解法二

递归遍历，head 为当前节点，将 next 的 next 作为 head 传入下一层递归，直到 head 或者 head 的 next 不存在，在递归体中将 next 的 next 设置为 head，并将 next 返回，赋值给前一层的 head 的 next，从而完成两两节点的交换。

如下图所示，实线为原指针，虚线为调整后的指针（由 4 开始）：

def swap_pairs(head):
    if not head or not head.next:
        return head
    next = head.next
    head.next = swap_pairs(next.next)
    next.next = head
    return next

执行用时 :56 ms
内存消耗 :13.7 MB

参考

https://leetcode-cn.com/problems/swap-nodes-in-pairs/