python算法-016把链表以k个节点为一组进行翻转不足k个也翻转

希望让人自由。——豆瓣电影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个人，通过一个工作人员，翻转了排队的顺序，但是手里的牌没变。

节点交换值法：这种方法很麻烦，但是也可以实现，目前想到两种：

1. 从头开始遍历，每次都把当前节点的值与其后继节点交换，直到到达最后一个节点，之后再从头遍历，直到倒数第2个节点，这样一直循环下去，直到最后一个节点到达第一个节点。有点相似排序的算法，但是这是翻转，前面的逆序链表也可以这么做。但是缺点非常显著：效率低，非常低，假如我k=100，k=1000,电脑会哭的。。。。比爬还慢，所以这不是我们要的。
2. 也是用两个指针，分别指向头和尾，交换着两个节点的值，而后在遍历第二个节点和倒数第二个节点，交换值，直到到达中间的节点。这让我想起了小学上课老师讲的高斯算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 randomimport timeclass LNode:    def __init__(self,arg):        self.data=arg        self.next=None"""题目形容：给定链表Head->1->2->3->4->5->7->7->8k=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=curdef 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 -= 1if __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张搞定，代理商池还没弄，多线程也不想弄了，爬添加服务器负担，反正数据量也不是太大，数据库还么想好用哪个，数据可视化还差点。。。。

电脑没电了，就不多说了。加油！