题目描述

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

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

示例:

给定 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

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        dummy = ListNode(0)
        cur = head
        pre = dummy
        # 确保两个节点能够交换，分别是cur和cur.next
        while cur and cur.next:
            # 保存好cur.next的后继结点，因为会产生断链，指向cur
            temp = cur.next.next
            # 前驱节点的后继指向第二个
            pre.next = cur.next
            # 第二个后继指向第一个
            cur.next.next = cur
            # 第一个后继指向保存的后继结点，接上
            cur.next = temp
            # 更新前驱节点为cur
            pre = cur
            # 当前需要交换的第一个节点就是保存的哪一个
            cur = temp
        return dummy.next