swapPairs.py

# 24. Swap Nodes in Pairs
# Author: Yu Zhou

# 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.
#
# 思路

# 这题的关键是处理每个Node的指针关系
# 设置3个pointer， p0也就是prev，p1是head, p2是next
# 然后把关系通过纸画下来，就能够理解个个pointer的关系了。
# 之前我的想法特别奇葩，在下面的代码里，感觉也没写对。。

# ****************
# Final Solution *
# ****************
classSolution(object):
defswapPairs(self, head):
ifnothead:
returnhead

guard=p0=ListNode(0)
guard.next=head

whilep0.nextandp0.next.next:
p1=p0.next#第一个交换数
p2=p0.next.next#第2个交换数

p0.next=p2
p1.next=p2.next
p2.next=p1

p0=p0.next.next

returnguard.next

# ***************************************
# The following code is an fail attempt *
# ***************************************
classSolution(object):
defswapPairs(self, head):
ifnothead:
returnhead

dummy1 , dummy2=ListNode(0), ListNode(0)

cur=head.next
whilecur:
dummy1.next=cur
ifcur.next:
cur=cur.next.next

cur=head
whilecurandcur.next:
dumm2.next=cur
cur=cur.next.next

#merge
dummy=ListNode(0)
dummy.next=head
whiledummy1anddummy2:
dummy.next=dummy1
dummy=dummy.next
dummy1=dummy1.next

dummy.next=dummy2
dummy=dummy.next
dummy2=dummy2.next

ifdummy1:
dummy.next=dummy1
ifdummy2:
dummy.next=dummy2

returndummy.next