蓝桥杯---链表3

1.题目再现

重拍链表就是对于这个链表里面的存在的节点元素进行顺序的重新排列：

假设我们原来的这个链表里面是存在着5个节点的，这个时候重新排列之后就是

1---5---2--4--3这样的顺序，就是从最前面和最后面依次取出来一个元素，按照这样的这个顺序进行拼接就可以了，因此我们就可以发现这个规律了，就是依次去取出来第一个，最后一个，新的第一个，新的最后一个，按照这个顺序组建一个新的链表，这个过程就是对于我们的原来的链表进行重排的过程，所以把这个称之为重排链表；

2.思路分析

这个题目可以作为一道很好的这个面试题目，因为这个题目很经典，分为几个主要的部分，很考验我们的综合能力，因为这个过程里面的每一个部分我们都是之前做过的，所以这个时候面试官可能就会使用这个题目作为一个面试的题目，考验大家手撕算法这个能力；

为什么说这个题目非常的综合呢，这个就是因为我们的这个过程划分为三个步骤：第一步就是找到这个链表里面的中间节点，因为这个链表我们需要根据中间节点划分为两个部分；

找到这个中间的节点之后，需要做的就是对于这个后面的部分进行逆序的操作，接下来就是万事俱备只欠东风，我们直接把这两个链表进行合并就可以了，而上面的这个过程里面的每一个步骤，我们之前都是单独命题的，也就是之前的一些小题都是有些过相关的这个题目的；

比如这个链表的中间节点如何去找，这个使用的就是我们的快慢指针的思想，之前是有相关的这个题目的，关于这个链表的逆序，就是去创建一个新的虚拟头节点，把原来的链表里面的节点尾插到我们的这个虚拟头结点的后面不就可以了吗；

至于这个链表的合并，也是使用的双指针，随着指针的移动，我们不断的让两个链表上面的对应位置的元素组成一个新的链表，这个新的链表就是我们的这个题目需要的最后的结果；

下面的这个是处理，我们如何进行逆序，从哪一个位置开始的？实际上这个是从slow的next位置开始进行这个逆序的，就是我们的这个next开始后面的这个链表需要进行逆序的操作；

实际上，这个我们是可以进行验证的，无非就是偶数个节点和奇数个节点两类情况，我们下面写出来了两个情况对应的这个例子：

首先就是这个偶数个节点，这个情况下，我们的slow.next指向的就是4这个元素，这个时候顺序依次就是1,4,23我们可以发现是没有任何的问题的；

对于奇数个节点，对于这个slow后面的内容进行逆序的操作，也就是45这个进行逆序，这个过程就是123和54分别作为两个链表，正好和我们的重排的结果是一致的，因此这个逆序的开始节点就是我们的中间节点的下一个位置开始；

下面的这个是关于我们的双指针寻找中间节点时候的这个判断条件的说明：这个也是分为了两个情况，一个就是我们的奇数个节点，此时的这个f的下一个不可以是空的，就是当我们的f下一个位置是空的时候我们的这个循环就需要停止，因为这个时候slow对应位置的元素就是中间的节点；

对于偶数个节点的情况，此时我们的这个f指向的元素不可以是空的，当我们的这个f指向的元素是空的时候，我们就需要跳出来这个循环，因为此时这个slow指向的位置的节点就是这个偶数个链表元素对应的中间节点；

下面的这个是说明的我们进行两个链表的合并的时候是如何进行头部插入数据的；先让cur指向我们的null，然后让这个虚拟头结点指向我们的这个cur，以此类推，每一次都是进行的头插的操作，最后的这个结果就是我们的这个原来的链表被逆序了；

3.代码分析

下面的这个代码是完全按照上面的思路展开的，首先就是把这个链表进行分段，分成两个短的链表，这个分段的原则就是从这个中间节点的位置；

刚开始的代码就是双指针找出来中间的节点，然后就是头插法对于右边的这个链表进行逆序，head2就是我们的逆序之后的链表的虚拟头结点，原来的这个正序节点都需要插入到这个head2的后面；

listnode next=cur.next记录下来这个next位置主要是为了防止cur的变化导致找不到这个节点，cur=next就是变化我们的原来链表里面的cur节点的位置，进行一下更新即可；

ret就是合并到的新的链表的这个头结点，原来的两个链表里面的节点就尾插到这个ret的后面即可，因为这个前面的链表是长的，所以只需要让这个while里面判断我们的cur1不是空的就可以了，cur2对应的这个链表短一些，所以这个需要进行一个if判断；