Swap Nodes in Pairs

题目描述

Given a linked list, swap every two adjacent nodes and return its head.

For example, Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

解题方法

相同于每次reverse两个node, 每次影响的是3个node, pre, node1 和 node2

所以不断地改变这三个node的关系，并且向后移，要注意是的判断结束的点.

• 每次两个node为一组，只要node2不为None, 就应该继续swap
• 当node2为None时，说明这一组的node1是tail node, 有奇数个node, 不需要再swap了
• 当node2.next为None时，说明已经到了结尾，有偶数个node

Solution

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head

        dummy = ListNode(0)
        dummy.next = head
        pre = dummy

        cur1 = head
        cur2 = head.next
        while cur2:
            tmp1 = cur2.next
            pre.next = cur2
            cur2.next = cur1
            cur1.next = tmp1

            if not tmp1:
                break
            else:
                pre = cur1
                cur1 = tmp1
                cur2 = cur1.next

        return dummy.next

Reference