LeetCode 24 [Swap Nodes in Pairs]

原题

给一个链表，两两交换其中的节点，然后返回交换后的链表。

样例
给出 1->2->3->4, 你应该返回的链表是 2->1->4->3。

解题思路

• 由于第一个节点要参与调换 => Dummy node帮忙
• 快慢指针，外加一个temp指针，倒来倒去。特别注意while循环的结束条件，不清楚可以用几个小的特殊的例子跑一下。

完整代码

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

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None or head.next == None:
            return head
        
        Dummy = ListNode(0)
        Dummy.next = head
        
        slow, fast = Dummy, Dummy.next
        while fast != None and fast.next != None:
            temp = fast.next.next
            slow.next = fast.next
            fast.next.next = fast
            fast.next = temp
            
            slow = fast
            fast = fast.next
        
        return Dummy.next