有关心情

题目描述：
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

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

说明：发现leetcode的代码运行时间、消耗内存统计对服务器状态依赖很大，同一份代码上一刻超越97%人，下一刻仅仅超过13%也是常有。参考意义不大，就不贴这些无意义的信息了。

第一种：拆分链表，再组装成新的链表。

class Solution:
    def swapPairs(self, head):
        node = head

        if node is None:
            return node
        elif node.next is None:
            return node

        # 第一步，拆分链表
        queue = []  # 利用队列特性：先进先出
        while node:
            if node.next is None:  # 如果只有一个元素，取一个
                queue.append([node])
                node = node.next
            elif node.next is not None:  # 如果两个元素，取两个
                queue.append([node, node.next])  # 不必在这儿交换node和node.next的位置，因为pop()总是先取出最后一个
                node = node.next.next

        queue.reverse()
        # 第二步，组装新链表
        afterHead, head = queue.pop()  # 做第一次交换，为的是留下head
        head.next = afterHead
        cur = head.next
        while queue:
            lyst = queue.pop()
            while lyst:
                cur.next = lyst.pop()
                cur = cur.next
        cur.next = None  # 循环结束后，需要把最后一个元素的next指向None

        return head

第二种：基于第一种方式的优化，将拆分链表与组装链表合在一起做。

import copy
class Solution:
    def swapPairs(self, head):
        node = head

        pre, pre.next = self, None  # pre.next即为链表头，绑定到self上
        while node:
            if node.next is None:  # 如果只有一个元素，取一个
                pre.next = node
                pre = pre.next
                node = node.next
            elif node.next is not None:  # 如果两个元素，取两个
                # 注意：需要深拷贝，否则造成循环引用，程序进入死循环
                lyst = [copy.deepcopy(node), copy.deepcopy(node.next)]
                while lyst:
                    pre.next = lyst.pop()
                    pre = pre.next
                node = node.next.next

        pre.next = None
        return self.next

第三种：（比较优雅的方法）

class Solution:
    def swapPairs(self, head):
        pre, pre.next = self, head
        while pre.next and pre.next.next:
            a, b = pre.next, pre.next.next
            # 交换结点，在交换后的右边结点位置续上没有交换的、剩余结点
            pre.next, pre.next.next, a.next = b, a, b.next
            pre = a  # 指针前进两个位置
        return self.next