python算法-010对链表进行重新排序

任何坏习惯、不好的行为，只有零次和无数次之分。——不知道谁说的

今天的题有点难度，我开始写的晚了。今天写爬虫遇到了麻烦，头疼了一天。今天发的晚了，停更只有零次和无数次之分！

题目描述：
给定链表L0->L2->L3……->Ln-1->Ln
把链表重新排序为L0->Ln->L2->Ln-1->L3->Ln-2……
要求：
（1）在原来链表的基础上进行排序，即不能申请新的节点；
（2）只能修改节点的next域，不能修改数据域

今天的题目的难度是有的，不过还在我们能理解的范围内。下面我们来分析下这道题目：要将链表的最后一位接在第一个节点后，首先很容易就能想到：分两重循环，第一重从链表头开始遍历，第二重就是从尾部开始遍历，然后将尾部节点直接连在外层遍历节点之后即可，直到链表到中间。当然你们会问怎么从尾部开始遍历？很简单，每次都遍历到最后一个，然后将其加到前面；然后下次遍历的时候，还是遍历到最后一个节点，因为最后一个节点就是我们需要处理的节点。那又有人问了，怎么判断是否到中间了呢？这也简单，先遍历链表算出链表的长度，然后去中值，然后再从头遍历到这个中值，这非常麻烦！！！
上面的方法是我写文章时临时想的，是不是看起来没什么问题，但是！！！实际操作起来，非常费时，费力，容易出错。而且会让人觉得我没有脑子。。。

下面正确方法：

观察题目的两个链表：L0->L2->L3……->Ln-1->Ln和L0->Ln->L2->Ln-1->L3->Ln-2……，可以想象一条绳子，上面有一个一个的结，我把绳子首尾对接，将绳子对折，是不是就大概像是题目的那样，节点位置改变了，当然题目要求更高点，要变成一条链表。对于链表，你不能说对折就对折了，自然是要想办法——>先将链表从中间断开，然后将后半条链表逆序，然后合并。注意！这里不是直接将其连到后面，而是将后面的每一个节点都插到两个节点之间。这里就涉及到连个重要的操作——如何判断链表的中间节点是哪个？以及如何合并两个链表？

先来看寻找中间节点的方法：前面已经介绍了一种简单的方法，但是需要遍历链表两次，不是我们想看到的情况。我们现在来看一个更快的方法：

1. 用两个指针——jump1和jump2。jump1每次向后遍历一个节点；jump2每次向后遍历两个节点。
2. 当jump2到达尾部时（这里会有两种情况，奇数个和偶数个，下面分析），jump1刚好是到达链表中间节点。

这里又分两种情况，链表长度为奇数和偶数，这两个是不一样的情况——数学问题：

• 奇数：jump2步长为2，最后一次刚好可以遍历到最后一个节点。此时的mid节点取jump1和jump1.next都行。
• 偶数：jump2步长为2，是无法遍历到最后一个节点的，只能遍历到倒数第二个节点，下一跳就为空了，可以结合下面的代码看一下：
  比如：1->2->3->4
  #在一次循环后jump2指向3，根据循环条件，此时是要再进入循环的，
  #这次循环是没问题的，也就是jump2指向None，但是此时来判断是否进循环就出了问题
  #因为jump2是空的，它没有next属性，程序在运行是会报错
  具体细节我在代码注释里写的非常清楚了！仔细看

    jump1 = head.next  # step为1的指针
    jump1Pre = head.next # 用于指向jump1的前驱节点
    jump2 = head.next  # step为2的指针
    mid = None # 用于指向链表的重点
    while jump2.next is not None:
        #这句是重点！！当链表长度为偶数，比如：1->2->3->4
        #在一次循环后jump2指向3，根据循环条件，此时是要再进入循环的，
        #这次循环是没问题的，也就是jump2指向None，但是此时来判断是否进循环就出了问题
        #因为jump2是空的，它没有next属性，程序在运行是会报错
        if jump2.next.next is None:
            break
        # 指向下一跳
        jump1Pre = jump1
        jump1 = jump1.next
        jump2 = jump2.next.next
    #这里接着上面的问题，无论是哪种情况退出循环
    # 其中间值我都设为jump1后一个，
    # 1）循环条件退出，说明个数为偶数，选jump1和jump1.next是一样的
    # 2）if语句退出，说明链表长度为奇数，但是jump2并没有到最后一个，
    #    所以其中间值应该是jump1的后一个，这是数学问题，大家自己画画图
    mid=jump1.next
    jump1Pre=jump1
    jump1Pre.next = None  # 切断

接下来就是逆序链表了——详情看 、、。

    #逆序后面的链表，这里就不多说了，前面都讲了三个方法了 
    cur=mid.next#用来逆序链表,指向第2个节点
    mid.next=None
    while cur is not None :
        next=cur.next
        cur.next=mid
        mid=cur
        cur=next

重点:合并两个链表

我直接上图了。上面的是前半部分，下面的是逆序后的后半部分：
链表长度为偶数时，前后两个链表合并时的处理顺序：

    # 这里是难点
    # 合并head和mid，mid无头节点
    curHead=head.next # 指向前半条链表的第一个节点
    curmid=mid # 指向后半条链表的第一个节点，从这里也可理解前面的mid节点的选取，
    #因为我要的是后半条，自然得要中间节点的后一个
    while curHead.next is not None:
        #因为取中间节点的原因，前半条链表的长度大于等于后半条
        nexthead = curHead.next #记录head的下一个节点
        #这里你看我前面画的图 
        curHead.next = curmid
        nextmid = curmid.next #记录mid的下一个节点
        curmid.next = nexthead
        curHead = nexthead
        curmid = nextmid
    # 这是前半条链表导等于后半条链表，
    # 也就是原链表产的长度为偶数的情况，因为前面循环只处理的
    # 只是将head连到mid，再从mid连到head，每次处理两个链接，
    # 但是偶数个节点之间应该有奇数个链接，这里是mid的最后一个节点没有处理
    if cur mid is not None:
        curHead.next=curmid
    return head

以上的代码我是写在了一个函数里，上面被我分开了，方便大家看。下面来试一试这个算法是否正确，我试了长度分别为：0，1，2，3，9，10，这几组：

if __name__ == '__main__':
    head=creatLink(5)
    print("BeforeReverse:")
    cur = head.next
    while cur != None:
        print(cur.data)
        cur = cur.next
    head=xReverese(head)
    print("\nAfterReverse:")
    cur = head.next
    while cur != None:
        print(cur.data)
        cur = cur.next

输出结果：

上面的这种输入可以检验我们的代码是否强壮，不能因为一次对了，就认为整个程序都对了。
全部的代码：

class LNode:
    def __init__(self,arg):
        self.data=arg
        self.next=None

"""
题目描述：
给定链表L0->L2->L3……->Ln-1->Ln
把链表重新排序为L0->Ln->L2->Ln-1->L3->Ln-2……
要求：（1）在原来链表的基础上进行排序，即不能申请新的节点；（2）只能修改节点的next域，不能修改数据域
方法：
先找到链表的中间节点，并将原链表拆分成两个子链表，将后面的子链表逆序，在将两个子链表合成最终链表
"""
def creatLink(x):
    i = 1
    head = LNode(None)
    tmp = None
    cur = head
    while i <= x:
        tmp = LNode(i)
        cur.next = tmp
        cur = tmp
        i += 1
    return head
def xReverese(head):
    #判断链表是否为空，或者只有一个元素，或者只有两个元素
    if head is None or head.next is None or head.next.next is None:
        return head
    # 寻找链表中间节点
    jump1 = head.next  # step为1的指针
    jump1Pre = head.next # 用于指向jump1的前驱节点
    jump2 = head.next  # step为2的指针
    mid = None # 用于指向链表的重点
    while jump2.next is not None:
        #这句是重点！！当链表长度为偶数，比如：1->2->3->4
        #在一次循环后jump2指向3，根据循环条件，此时是要再进入循环的，
        #这次循环是没问题的，也就是jump2指向None，但是此时来判断是否进循环就出了问题
        #因为jump2是空的，它没有next属性，程序在运行是会报错
        if jump2.next.next is None:
            break
        # 指向下一跳
        jump1Pre = jump1
        jump1 = jump1.next
        jump2 = jump2.next.next
    #这里接着上面的问题，无论是哪种情况退出循环
    # 其中间值我都设为jump1后一个，
    # 1）循环条件退出，说明个数为偶数，选jump1和jump1.next是一样的
    # 2）if语句退出，说明链表长度为奇数，但是jump2并没有到最后一个，
    #    所以其中间值应该是jump1的后一个，这是数学问题，大家自己画画图
    mid=jump1.next
    jump1Pre=jump1
    jump1Pre.next = None  # 切断

    #逆序后面的链表，这里就不多说了，前面都讲了三个方法了 
    cur=mid.next#用来逆序链表,指向第2个节点
    mid.next=None
    while cur is not None :
        next=cur.next
        cur.next=mid
        mid=cur
        cur=next

    # 这里是难点
    # 合并head和mid，mid无头节点
    curHead=head.next # 指向前半条链表的第一个节点
    curmid=mid # 指向后半条链表的第一个节点，从这里也可理解前面的mid节点的选取，
    #因为我要的是后半条，自然得要中间节点的后一个
    while curHead.next is not None:
        #因为取中间节点的原因，前半条链表的长度大于等于后半条
        nexthead = curHead.next #记录head的下一个节点
        #这里你看我前面画的图 
        curHead.next = curmid
        nextmid = curmid.next #记录mid的下一个节点
        curmid.next = nexthead
        curHead = nexthead
        curmid = nextmid
    # 这是前半条链表导等于后半条链表，
    # 也就是原链表产的长度为偶数的情况，因为前面循环只处理的
    # 只是将head连到mid，再从mid连到head，每次处理两个链接，
    # 但是偶数个节点之间应该有奇数个链接，这里是mid的最后一个节点没有处理
    if cur mid is not None:
        curHead.next=curmid
    return head

if __name__ == '__main__':
    head=creatLink(5)
    print("BeforeReverse:")
    cur = head.next
    while cur != None:
        print(cur.data)
        cur = cur.next
    head=xReverese(head)
    print("\nAfterReverse:")
    cur = head.next
    while cur != None:
        print(cur.data)
        cur = cur.next

今天晚了，因为内容比较多，我也不想糊弄自己，更不想糊弄大家，我是不会停更的！！！
加油！！！

还是那样，我一如既往的乐于帮助大家——微信、简书：Dkider。语句千万条，正确第一条。代码不规范，手指两行泪。