[Leetcode][python]Swap Nodes in Pairs/两两交换链表中的节点

àì夳堔傛蜴生んèń 2022-06-09 11:27 41阅读 0赞

## 题目大意 ##

交换链表中相邻的两个元素。  
注意第一个节点与第二个节点要交换位置，而第二个节点不用与第三个节点交换位置。  
注意点：  
不允许修改节点的值  
只能用常量的额外空间

## 解题思路 ##

该题费脑，绕来绕去的指向，这个解读比较清晰  
来自：  
[https://shenjie1993.gitbooks.io/leetcode-python/024%20Swap%20Nodes%20in%20Pairs.html][https_shenjie1993.gitbooks.io_leetcode-python_024_20Swap_20Nodes_20in_20Pairs.html]  
比较常见的链表操作。下面看一下典型情况，如要交换链表中A->B->C->D中的B和C需要做如下操作：

*  将A指向C
 *  将B指向D
 *  将C指向B

在头节点之前加一个假节点就可以使所有的交换都符合上面的情况。

## 代码 ##

class Solution(object):
        def swapPairs(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            dummy = ListNode(-1)
            dummy.next = head
            temp = dummy 
            while temp.next and temp.next.next:
                node1 = temp.next  # node1是B
                node2 = temp.next.next  # node2是C
                temp.next = node2  # A指向C
                node1.next = node2.next  # B指向D
                node2.next = node1  # C指向B
                temp = temp.next.next  # 跳过两个
            return dummy.next

## 总结 ##

[https_shenjie1993.gitbooks.io_leetcode-python_024_20Swap_20Nodes_20in_20Pairs.html]: https://shenjie1993.gitbooks.io/leetcode-python/024%20Swap%20Nodes%20in%20Pairs.html