大鹏一日同风起，扶摇直上九万里。
假令风歇时下来，犹能簸却沧溟水。
世人见我恒殊调，闻余大言皆冷笑。
宣父犹能畏后生，丈夫未可轻年少。
——李白《上李邕》
在现代，别人对你的文章冷嘲热讽，你来一句：“你行你上啊！”他可能就没脾气了。但是要换李白，他真的会上，因为他真的行！
题目描述：将链表的每两个节点翻转。不允许用新的节点。
例如：
给定链表Head->1->2->3->4->5->7->7->8
反转为链Head->2->1->4->3->7->5->8->7
这题是为了明天的题目做铺垫的，先来分析下这个题：本质上还是操作链表，之前我们做过类似的。不过，这次是翻转节点，节点有两个属性data和next，交换两个节点的值就可以完成了，这样不需要将节点位置改变。这太简单了，就像a=1,b=2,交换a,b的值一样那么简单，只需要用一个中间值tmp来保存就行：tmp=a a=b b=tmp。主要的问题就是如何遍历的问题，这也是个不是问题的问题。用一个指针即可完成，但是对于明天的题，并没有太大帮助。
下面来看利用next属性，如何做：
利用next属性必然会改变节点的位置，也就是链表结构会变，先来看看怎样改变
主两个指针，更好理解
图中我用红笔标出了操作顺序1、2、3、4：先pre->fast，然后fast->slow，最后slow->next，这里为什么会先把next->fast.next:因为在第二步时，得保存后面的链表，不然会丢失，这与a.b交换值是一个道理。这里的顺序也可以换成1、2、4、3，两个效果是一样的。
这里有一个注意的地方就是每次的循环条件：宗旨就是当后面的节点不够一组进行交换时，退出循环。但是如何知道后面不够一组呢？先来看下代码。
下面代码实现：
def function(head):
#判断链表是否为空，为空返回
if head.next is None or head.next.next is None:
return head
pre=head # 指向slow的前驱节点
slow=head.next
fast=slow.next
#slow和fast为相邻的节点
#next=fast.next
# 这里的循环条件要注意
# 链表的长度可能为奇数，也可能是偶数
# 每次四个指针会变换，因为是先操作再迭代下一组
# 再迭变换完后，如果fast指针后面只有一个元素，或者没有元素，这时
# 后面的无法再进行翻转，所以应该出循环，正常应该做完在判断的，
# 这里只能符合的才操作，因为用的指针多了一个。
while fast.next is not None and fast.next.next is not None:
next = fast.next #保存链表，因为要断开
pre.next=fast
fast.next=slow
slow.next=next
# # 上面的四句做的操作，见图
pre=slow
slow=next
fast=slow.next
#因为面的判断条件，最后一组，我们并没有翻转，这里操作下
next = fast.next
pre.next = fast
fast.next = slow
slow.next = next
return head
这里我用while fast.next is not None and fast.next.next is not None，这一句看起来很臃肿。
一组
这里我用了四个指针，链表的长度可能为奇数，也可能是偶数，每次四个指针会变换，因为是先操作再迭代下一组，在变换完后，如果fast指针后面只有一个元素，或者没有元素，这时后面的无法再进行翻转，所以应该出循环，按分析应该做完在判断的，但是因为涉及到一个next指针，每次都得确定还有next,才能操作，不然会报错，这里我还没找到一个好的解释办法。要注意的是，最后一组没有换位置，可以把最后的四行语句注释掉，看看结果就知道了。
image.png
鉴于此，我把指针减少了，只用一个主指针cur，用（cur，cur.next)这样一组来代替slow，fast。
这样的好处是，不用考虑fast是否有next.next,只看cur就行。操作是一样的：
image.png
代码实现：
def function(head):
if head is None or head.next is None:
return head
cur=head.next#当前遍历节点
pre=head#当前遍历节点的前驱节点
next=None#当前节点后继节点的后继节点
# 这里的循环条件可能不太一样，因为省掉了fast,所以考虑的东西就会变少。
while cur is not None and cur.next is not None:
next=cur.next.next
pre.next=cur.next
#这里可能一看不太好理解
# （cur.next).next
# 这样把cur.next看做一个节点，也就是之前的fast
cur.next.next=cur
cur.next=next
pre=cur
cur=next
return head
循环条件变了，我将他们放在一个文件里了，如果后者没问题，就可以把变换的链表变回去：
if __name__ == '__main__':
head = creatLink(6)
print("head:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
head = function_1(head)
print("\nAfterReverse_1:") # 这是用slow和fast的
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
head = function_2(head) # 这是cur
print("\nAfterReverse_2:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
输出结果：
image.png
全部代码：
import random
class LNode:
def __init__(self,arg):
self.data=arg
self.next=None
"""
题目描述：
给定链表Head->1->2->3->4->5->7->7->8
反转为链Head->2->1->4->3->7->5->8->7
要求：
方法：只用一个cur,用pre和next辅助反转。
"""
def creatLink(x):
i = 1
head = LNode(None)
tmp = None
cur = head
while i <= x:
n = random.randint(1, 9)
tmp = LNode(n)
cur.next = tmp
cur = tmp
i += 1
return head
#
#双指针法
def function_1(head):
#判断链表是否为空，为空返回
if head.next is None or head.next.next is None:
return head
pre=head # 指向slow的前驱节点
slow=head.next
fast=slow.next
#slow和fast为相邻的节点
#next=fast.next
# 这里的循环条件要注意
# 链表的长度可能为奇数，也可能是偶数
# 每次四个指针会变换，因为是先操作再迭代下一组
# 再迭变换完后，如果fast指针后面只有一个元素，或者没有元素，这时
# 后面的无法再进行翻转，所以应该出循环，正常应该做完在判断的，
# 这里只能符合的才操作，因为用的指针多了一个。
while fast.next is not None and fast.next.next is not None:
next = fast.next #保存链表，因为要断开
pre.next=fast
fast.next=slow
slow.next=next
# # 上面的四句做的操作，见图
pre=slow
slow=next
fast=slow.next
#因为面的判断条件，最后一组，我们并没有翻转，这里操作下
next = fast.next
pre.next = fast
fast.next = slow
slow.next = next
return head
def function_2(head):
if head is None or head.next is None:
return head
cur=head.next#当前遍历节点
pre=head#当前遍历节点的前驱节点
next=None#当前节点后继节点的后继节点
# 这里的循环条件可能不太一样，因为省掉了fast,所以考虑的东西就会变少。
while cur is not None and cur.next is not None:
next=cur.next.next
pre.next=cur.next
#这里可能一看不太好理解
# （cur.next).next
# 这样把cur.next看做一个节点，也就是之前的fast
cur.next.next=cur
cur.next=next
pre=cur
cur=next
return head
if __name__ == '__main__':
head = creatLink(6)
print("head:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
head = function_1(head)
print("\nAfterReverse_1:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
head = function_2(head)
print("\nAfterReverse_2:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
铺垫就到这里，明天的题目是：
将链表以k个一组翻转，不足k个也翻转，
给定链表Head->1->2->3->4->5->7->7->8
k=3
反转为链Head->3->2->1->7->5->4->8->7
会吗？
今天就这样，更多题目见GitHub,简书、微信：DKider。
Data Knowledge idea(我故意打的r),这是我寒假想的名字，还挺好，之前没有什么实际意义，现在它有了！
我会尽量加快写的速度，我还要留时间学其他的知识。加油吧！
网友评论