希望让人自由。——豆瓣电影top250.No.1《肖申克的救赎》
很好看的电影，书也很好看，但我个人不太喜欢斯蒂芬·金的其他作品。。。。
题目描述：
给定链表Head->1->2->3->4->5->7->7->8
k=3
反转为链Head->3->2->1->7->5->4->8->7
要求：不足k个也翻转
今天的题目是昨天的延伸——015，昨天我们有两种方法，来翻转相邻的节点，一个是交换两个节点的值，一个是交换连个节点的位置。而交换节点的位置又有两种，一是用两个指针分别指着链表头和链表尾，还有一种是用一个指针指向头节点，尾节点用node.next来表示。
今天不在是相邻的两个节点了，而是k个，也就是从2个节点的简便方法提升到了k个节点的通法，k=0,1,2,3,4,5……
这题要求是以k个一组翻转，可以理解为，将这k个节点构成的子链表逆序，再放回原来的位置。
昨天的三个方法，理论上讲，都是可行的，我没有都试过：
可以想象有一群人，每个人手里有一张牌，上面写了数字，然后他们排成一列，
- 交换节点值法：这是不改变链表链接的顺序，只改变节点存储的数据，可以理解为只是每个人把手里的牌交换了，但是这些人站的位置没有变。
- 首尾指针法： 这改变了链表链接的顺序，节点自身的数据没改，可以理解为:这k个人，通过两个工作人员的帮助，翻转了排队的顺序，但是手里的牌没变。
- 首指针法： 这也改变了链表链接的顺序，节点自身的数据也没改，可以理解为:这k个人，通过一个工作人员，翻转了排队的顺序，但是手里的牌没变。
节点交换值法：这种方法很麻烦，但是也可以实现，目前想到两种：
- 从头开始遍历，每次都把当前节点的值与其后继节点交换，直到到达最后一个节点，之后再从头遍历，直到倒数第2个节点，这样一直循环下去，直到最后一个节点到达第一个节点。有点类似排序的算法，但是这是翻转，前面的逆序链表也可以这么做。但是缺点非常明显：效率低，非常低，如果我k=100，k=1000,电脑会哭的。。。。比爬还慢，所以这不是我们要的。
- 也是用两个指针，分别指向头和尾，交换着两个节点的值，然后在遍历第二个节点和倒数第二个节点，交换值，直到到达中间的节点。这让我想起了小学上课老师讲的高斯算1+2+3+4+……+100的故事。这种方法效率比上面的高一丢丢，但还是慢，就像一个是爬的，一个是拄着拐杖走的，这也不是我们要的！
（翻转完节点后要将其放回链表中，一会说）
我们要什么？我们要走，要跑的，要坐车，要坐飞机，要坐火箭，我们要上天！！
这么蠢的办法，当然不适合我们，因此我们推出了新的方法：
首指针法：这个方法在昨天，我们用的非常好，我们用一个指针指向当前的k个节点的第一个节点，将其从链表中断开，单独拿出来，用我们之前讲的——递归、就地逆序、插入法，将它逆序，然后在放回链表中，进行下一组，唯一缺点就是：在将它与下一组相链接时，需要从头遍历到最后一个节点，才能操作。不过这种方法也还行了。
真快！就像坐飞机一样，但是，我们要坐火箭！
首尾指针法：这个方法在昨天饱受诟病，今天我们将在它的带领下，坐上火箭，走向人生巅峰！从前面的单指针法，也就是首指针法中，我们看到，缺点是在链接回链表的时候，需要找他的尾结点。这增加的时间复杂度，那如果我们在开始遍历时就先同一个指针保存这个节点呢？
在完成翻转后，这个节点到了第一位：看下图：
image.png
一目了然，我们保存了尾结点，在翻转完成后，头变尾，尾变头，直接相连就OK。起飞！
但是，这找k个节点的尾结点的步骤不会增加时间？这就用到了我们之前讲的——寻找链表倒数第K个元素中的方法了，先后指针法！
起飞！起飞！
下面来看下代码实现：
def function(head,k):
if head.next is None:
return head
pre = head # 组前点
slow = head.next # 组的第一个节点
fast = head.next # 组的最后个节点
next = None
p = k
# 判断是否够一组,这一步是之前写的，现在我有点忘了，我索性全放上来了，反正这不能去掉，我也没细想。当然你想也可以去掉试试！
while p - 1 > 0:
# fast = fast.next # 这里
# fast = fast.next 究竟是放前面还是放后面，这里就非常讲究了，
# 在这里放前面放后面作用是一样的，因为，前面第一条把只有一个节点的情况直接过滤了
# 所以这里不会出现fast为None,而报出没有next属性的错误，但是在超过一组的情况中
# 不能过滤掉还剩一个的情况，只能先判断后翻转，所以如果放前面就会出现直
# 接把第一个节点直接跳过的情况
if fast.next is None:
# 不足一组
Reverse(slow)
head.next = fast
return head
fast = fast.next
p -= 1
# 一组以上
while True:
# 用来指向下一组的第一个节点
next = fast.next
# 断开与上一组的链接 可以不用断，不断开的话在翻转时pre.next但是断开来理解更形象
# pre.next=None
# 断开与下一组的链接
fast.next = None
# 翻转当前组的链表
Reverse(slow)
# 将当前链表与链表尾部相连
pre.next = fast
# 将pre移至链表尾部，因为翻转fast指向了组中第一个节点，slow则指向了最后一个
pre = slow
# 链接当前组与下一组 这里也很精髓 ，可以直接去掉，可以连也可以不连，反正一会得断掉
# pre.next=next
# 判断next是否为空 这里是精髓，就像判断链表是否为空一个道理，一开始我忘了。
if next is None:
return head
# 将slow指向下一组的第一个节点
slow = next
fast = slow
# 判断后面是否还有一组
p = k
while p - 1 > 0:
# 不够一组翻转并推出
# fast = fast.next
if fast.next is None:
# pre.next = None
# 翻转
Reverse(slow)
# 将当前组链接至链表尾部
pre.next = fast
return head
fast = fast.next
p -= 1
主函数：
if __name__ == '__main__':
head = creatLink(10)
print("head:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
k=int(input("请输入k值：\n"))
start=time.time()
head = function(head,k)
end=time.time()
print("用时",start-end)
print("\nAfterReverse:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
运行结果：
image.png
全部代码:
import random
import time
class LNode:
def __init__(self,arg):
self.data=arg
self.next=None
"""
题目描述：
给定链表Head->1->2->3->4->5->7->7->8
k=3
反转为链Head->3->2->1->7->5->4->8->7
要求：不足k个也翻转
方法：
"""
def creatLink(x):
i = 1
head = LNode(None)
tmp = None
cur = head
while i <= x:
n = random.randint(1, 9)
tmp = LNode(n)
tmp = LNode(i)
cur.next = tmp
cur = tmp
i += 1
return head
# 以k个元素为一组进行翻转，可以理解为每一个子链表的逆序
# 逆序链表
def Reverse(head):
# 判断链表时否为空，为空返回
if head is None or head.next is None:
return
cur = None # 用于遍历链表
pre = None # 指向当前节点的前驱节点
next = None
#处理第一个节点
cur = head
next = cur.next
cur.next = None
pre = cur
cur = next
while cur.next != None:
next = cur.next
cur.next = pre
pre = cur
cur = next
#添加头节点
cur.next = pre
head=cur
def function(head,k):
if head.next is None:
return head
pre = head # 组前点
slow = head.next # 组的第一个节点
fast = head.next # 组的最后个节点
next = None
p = k
# 判断是否够一组
while p - 1 > 0:
# fast = fast.next # 这里
# fast = fast.next 究竟是放前面还是放后面，这里就非常讲究了，
# 在这里放前面放后面作用是一样的，因为，前面第一条把只有一个节点的情况直接过滤了
# 所以这里不会出现fast为None,而报出没有next属性的错误，但是在超过一组的情况中
# 不能过滤掉还剩一个的情况，只能先判断后翻转，所以如果放前面就会出现直
# 接把第一个节点直接跳过的情况
if fast.next is None:
# 不足一组
Reverse(slow)
head.next = fast
return head
fast = fast.next
p -= 1
# 一组以上这一步是之前写的，现在我有点忘了，我索性全放上来了，反正这不能去掉，我也没细想。当然你想也可以去掉试试！
while True:
# 用来指向下一组的第一个节点
next = fast.next
# 断开与上一组的链接 可以不用断，不断开的话在翻转时pre.next但是断开来理解更形象
# pre.next=None
# 断开与下一组的链接
fast.next = None
# 翻转当前组的链表
Reverse(slow)
# 将当前链表与链表尾部相连
pre.next = fast
# 将pre移至链表尾部，因为翻转fast指向了组中第一个节点，slow则指向了最后一个
pre = slow
# 链接当前组与下一组 这里也很精髓 ，可以直接去掉，可以连也可以不连，反正一会得断掉
# pre.next=next
# 判断next是否为空 这里是精髓，就像判断链表是否为空一个道理，一开始我忘了。
if next is None:
return head
# 将slow指向下一组的第一个节点
slow = next
fast = slow
# 判断后面是否还有一组
p = k
while p - 1 > 0:
# 不够一组翻转并推出
# fast = fast.next
if fast.next is None:
# pre.next = None
# 翻转
Reverse(slow)
# 将当前组链接至链表尾部
pre.next = fast
return head
fast = fast.next
p -= 1
if __name__ == '__main__':
head = creatLink(10)
print("head:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
k=int(input("请输入k值：\n"))
#k=3
start=time.time()
head = function(head,k)
end=time.time()
print("用时",start-end)
print("\nAfterReverse:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
好了，今天的算法就到这里。
上周末的爬虫写的差不多了，数据清洗搞定，下载海报30张搞定，代理池还没弄，多线程也不想弄了，爬增加服务器负担，反正数据量也不是太大，数据库还么想好用哪个，数据可视化还差点。。。。
电脑没电了，就不多说了。加油！
网友评论