任何坏习惯、不好的行为，只有零次和无数次之分。——不知道谁说的
今天的题有点难度，我开始写的晚了。今天写爬虫遇到了麻烦，头疼了一天。今天发的晚了，停更只有零次和无数次之分！
题目描述：
给定链表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……，可以想象一条绳子，上面有一个一个的结，我把绳子首尾对接，将绳子对折，是不是就大概像是题目的那样，节点位置改变了，当然题目要求更高点，要变成一条链表。对于链表，你不能说对折就对折了，自然是要想办法——>先将链表从中间断开，然后将后半条链表逆序，然后合并。注意！这里不是直接将其连到后面，而是将后面的每一个节点都插到两个节点之间。这里就涉及到连个重要的操作——如何判断链表的中间节点是哪个？以及如何合并两个链表？
先来看寻找中间节点的方法：前面已经介绍了一种简单的方法，但是需要遍历链表两次，不是我们想看到的情况。我们现在来看一个更快的方法：
- 用两个指针——jump1和jump2。jump1每次向后遍历一个节点；jump2每次向后遍历两个节点。
- 当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
重点:合并两个链表
我直接上图了。上面的是前半部分，下面的是逆序后的后半部分：
链表长度为偶数时，前后两个链表合并时的处理顺序：
链表长度为偶数
这里我是将两个操作合在一起，作为一次循环做的工作，还可以将1步作为一次循环方法。很多书上是后者，我觉得对于新书，我还是两步操作看的更清楚！从图上可以看到5这个节点我并没有接上，因为在我的循环里它完不成，需要在结束后再接上。图中若是把5这个节点直接拿掉，就是奇数长度的链表的操作过程。以上，看图细细体会。
代码：
# 这里是难点
# 合并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
输出结果：
0
1
3
9
10
上面的这种输入可以检验我们的代码是否强壮，不能因为一次对了，就认为整个程序都对了。
全部的代码：
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。语句千万条，正确第一条。代码不规范，手指两行泪。
Dkider
网友评论