交换链表中相邻的两个元素。 注意第一个节点与第二个节点要交换位置,而第二个节点不用与第三个节点交换位置。 注意点: 不允许修改节点的值 只能用常量的额外空间
该题费脑,绕来绕去的指向,这个解读比较清晰 来自: https://shenjie1993.gitbooks.io/leetcode-python/024%20Swap%20Nodes%20in%20Pairs.html 比较常见的链表操作。下面看一下典型情况,如要交换链表中A->B->C->D中的B和C需要做如下操作:
在头节点之前加一个假节点就可以使所有的交换都符合上面的情况。
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