【数据结构】使用归并排序对链表进行排序

首先我们要看一道题 对于我们解题很重要

 while循环是固定的。

 这道题没毛病看到都知道用双指针,但是快慢结点的初始赋值是怎么样的呢。

(1)奇数项 fast=head

 

 

 没毛病 3是中点。

(2)偶数项 fast=head(要求slow为中点的两个的第二个)

 

 

 

 符合条件。

来看归并排序链表

 如果我们还用刚才的fast=head会发生2个元素无法分开的情况

 

 会出现上图的情况。右链表一直空,左链表一直递归下去 栈溢出。

所以,我们根据题意 ,slow不应该和876题一样 要最中间的结点,应该要876中点的前一个结点。所以fast=head.next

 我们来看一个奇数项的完整版

 

 

 接下来就是进行递归拆分了。

写上面的理由就是:不要发生 无法分解为1个结点的情况(比如刚才2结点无法分 栈溢出)

原文地址:https://www.cnblogs.com/cckong/p/14455339.html