归并排序非递归排序链表

归并排序通常用于数组，但在处理链表时，由于链表的特点（节点间不是连续存储的），我们可以将其转换成一种迭代的方式来实现非递归的归并排序。这种方法被称为“归并排序迭代版本”或“分治法在链表上的应用”。

基本步骤如下：

1. **分解** (Divide): 将链表不断二分拆分成更小的两部分，直到每个部分只有一个元素。

2. **合并** (Conquer): 对每一对相邻的子链表进行合并操作。合并两个已排序的链表，创建一个新的链表，其节点值是由原两个链表对应节点值较小的一个组成，然后将新链表链接到结果链表上。

3. **整合** (Combine): 当所有子链表合并完毕后，我们就得到了最终的有序链表。

关键在于合并过程，需要借助三个指针（两个子链表头和结果链表头）来遍历和连接节点。由于链表无法像数组那样直接索引，所以每次合并都需要从头开始比较节点值。