算法思路

• 判断一个链表是否有环

使用2个指针同时遍历链表,前一个指针移动的速度是后一个指针的2倍,这样如果有环,就可以相遇,例如操场的环形跑道

• 求最大公约数
  1. 质因数分解法
  2. 短除法
  3. 辗转相除法(欧几里德算法): 两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数
  4. 更相减损法: 两个正整数a和b（a>b），它们的最大公约数等于a-b的差值c和较小数b的最大公约数
• 外部排序
  1. 按照内存大小，将大文件分成若干长度为 l 的子文件（l 应小于内存的可使用容量），然后将各个子文件依次读入内存，使用适当的内部排序算法对其进行排序（排好序的子文件统称为“归并段”或者“顺段”），将排好序的归并段重新写入外存，为下一个子文件排序腾出内存空间
  2. 对得到的顺段进行合并，直至得到整个有序的文件为止