数据结构之链表操作大集合（技术连载数据结构）

导读链表反转此题属于中低难度的题，思路并不复杂，单其中有很多易错点，比如空指针判断、指针丢失等；思路：设置三个指针pre、cur、next，初始时刻pre=nu....链表反转

此题属于中低难度的题，思路并不复杂，单其中有很多易错点，比如空指针判断、指针丢失等；

思路：设置三个指针pre、cur、next，初始时刻pre = null，cur = head;

开始处理，首先执行next = cur.next，防止后面cur.next修改之后指针丢失；

链表反转

环形链表检测并返回入环点

这个题目技巧性很强，一般不太容易想到；大体思路如下：

首先设置快慢指针，每一次移动，快指针移动两步（尤其需要注意第二步判断空指针），慢指针移动移步；然后判断两个指针是否指向同一位置。

如果最终快指针遇见null，则无环；如果快慢指针指向了同一位置，则有环；

如果有环的化，两指针相遇时，快指针移动到head位置，并且变为慢指针（每次移动一步）；然后两个指针再次开始移动，直到再次相遇即为入环点。（证明略）

环形链表检测

链表归并排序

二路归并排序：假设两个有序数组，设置两个指针，指向0位置，将指向比较小元素的指针对应的元素存入数组，并移动指针；直到两个指针移动完毕；

归并排序思路：归并排序是建立在二路归并排序基础之上，将数组逐渐分解，直到仅有一个元素，然后进行二路归并排序。（先分后合的思想）

伪代码如下：

public int[] merge(int[] nums,int start, int end){

if(start == end){

return new int[]{nums[start]};

}

int mid = (start end) / 2;

int[] s1 = merge(nums, start,mid);

int[] s2 = merge(nums,mid 1, end);

return binMerge(s1,s2);

}

链表归并排序比数组归并排序难度有所增加，但思路是一致的，仍然是逐步分解，直到只有一个结点，然后再合并。

主要区别在于中点的选取，关于中点选取，这里也有现成的思路，通过快慢指针，当快指针走到终点时，慢指针即为中点。

具体实现如下：

连载系列：

技术连载：开篇词

技术连载：连载提纲设计思路

技术连载：数据结构 - 数组

技术连载：数据结构 - 数组常见面试题汇总

技术连载：数据结构 - 链表