@author: ZZQ
@software: PyCharm
@file: swapPairs.py
@time: 2018/10/20 19:49
说明：给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
说明:
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
思路：
四个节点，分别记录当前需要进行交换的两个节点（first, second），以及这俩个节点的前后节点(pre, post)
然后每次只针对这四个节点进行交换即可。
注意考虑当输入是空节点，一个节点，两个节点，三个节点以及节点个数为奇数的情况。
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def __init__(self):
pass
def exchange(self, pre, first, second, post):
first.next = None
second.next = None
first.next = post
second.next = first
pre.next = second
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None or head.next is None:
return head
pre = ListNode(0)
pre.next = head
first = head
second = head.next
post = second.next
p = pre
while True:
self.exchange(pre, first, second, post)
pre = pre.next.next
first = pre.next
if first is None:
break
second = pre.next.next
if second is None:
break
post = post.next.next
if post is None:
self.exchange(pre, first, second, post)
break
return p.next
if __name__ == "__main__":
answer = Solution()
l1 = ListNode(1)
p1 = ListNode(2)
p2 = ListNode(3)
p3 = ListNode(4)
p4 = ListNode(5)
p5 = ListNode(6)
l1.next = p1
p1.next = p2
p2.next = p3
p3.next = p4
p4.next = p5
l2 = answer.swapPairs(l1)
while l2 is not None:
print l2.val
l2 = l2.next