蓝桥杯---链表题目

1.题目概述

这个题目是两两交换链表里面的节点：这个给定的实例里面这个链表的节点顺序就是1234，交换之后就是2143，这个交换的顺序就是前面的两个进行交换，后面的两个进行交换；

可能这个题目理解起来并不是很苦难，但是我觉得这个题目想要实现真的是有一定的难度的（你可以先自己实现以下，体会一下这个难度，因为我觉得这个题目里面需要我们考虑的这个细节还是比较多的）

2.案例分析

上面我们看到的是这个基本的一个交换的逻辑，但是我们还是需要考虑一些特殊的情况的：例如下面的这个示例二，如果这个链表是空的，这个时候我们的返回值也是一个空的，因为这个时候链表里面压根就没有任何的元素；

当这个链表里面只有一个元素的时候，这个时候单独一个元素是无法完成这个交换的过程的，所以返回的这个链表就是它本身，这个时候是不需要进行任何的这个额外的操作的；

上面的两个情况就是我们的这个链表里面的元素进行交换时候的两个特殊的情况

题目给定的案例

3.思路分析

这个思路很简单，看起来不难，主要就是你能不能想到了，我觉得，如果你是第一次学习这个内容的时候，你会觉得这个代码好像你也是可以理解的，但是这个你自己独立实现确实是有难度的，而且这个题目考验你对于这个链表的指针的理解，为什么需要创建一个虚拟的头结点，这些问题你是不是能够想明白呢？

首先我们需要创建一个虚拟的头结点，这个节点存在的目的就是为了帮助我们去处理这个头指针的相关问题，分别定义四个指针指向四个相关的元素（我们以这个题目里面给定的这个示例一进行思路分析，再去考虑里面的特殊的情况）；

分别列举出来这个交换前和交换之后的这个数据的排列的顺序：

这个交换的过程实际上就是我们的这个next和cur指向的元素的位置发生了变化，原来的这个cur在前面，next在后面，但是交换之后的结果就是next在前面，cur在后面，这个实际上就是指针的指向的变化；

但是我们的这个过程需要一直进行下去，这个过程肯定是不止一次的，所以我们的这个指针需要继续的向后面移动，继续进行判断，这个具体的移动方式呢？就是我们的prev指向我们的2，因为接下来相当于就是3,4进行交换，这个2相当于就是相当于一个“虚拟头结点”，所以这个时候prev需要指向我们的next的位置，cur指向我们的需要交换的第一个元素，也就是3的位置，即nnext的位置；

下面分别展示了两个终止的因素：一个是cur=null的时候，就是下面的这个绿色的笔画的第一个情况，这个情况下对应的就是我们有偶数个元素在我们的链表里面；

还有一个就是我们的链表里面有奇数个节点，这个时候的终止条件就是下面的这个next=null的时候，此时我们的这个循环应该是结束的；

4.代码解释

首先创建一个虚拟的头结点，然后去定义这个虚拟头结点指向我们的链表里面的head节点，也就是我们函数传递进来的这个参数，head是我们的这个链表里面的第一个有效的节点；

接下来就是分别定义四个节点和他们之间的这个相互的指向的关系，循环的终止条件就是我们上面介绍了的两个情况，前面的三行表示的就是交换之后的这个顺序；

while循环里面的中间两行就是我们的指针的移动：prev=cur,cur=nnext，这个表示的就是我们需要开启新一轮的这个循环；

因为这个会出现空指针的情况，所以我们添加了这个if进行条件的判断，最后的返回值就是我们的这个newhead后面的这个位置，也就是我们的链表里面的第一个有效元素的位置；