归并算法在于链表排序

题目：对链表进行排序。

示例 1:
输入: 4->2->1->3
输出: 1->2->3->4

单向链表在排序的时候，往往因为其特殊的next指针，弄的头脑很混乱，其实一般来说有两种方式来考虑链表排序中指针问题

1. 不考虑指针
   数据排序相对容易，因为我们可以很方便的通过数组长度进行遍历，并不断的做大小比较和交换，链表其实也可以利用这个思路。链表排序的时候可以不考虑指针的变动，而只进行值的交换。对于上面这个问题，我们可以通过遍历整个链表，采用冒泡排序的方式，只进行值交换，不改变现有引用关系，将大值数据赶到最右边：

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null) {
            return head;
        }

        ListNode comparedNode = head;
        while (comparedNode != null) {
            /*
              comparedNode用来表示当前我们关注的节点，
              我们将这个节点与后一个节点进行比较，如果
              发现后一个节点比关注节点小，那么我们调换
              两个节点值的顺序，并移动comparedNode
            */
            comparedNode = head;
            /*
              flag作为一个标志为，如果在从head往tail遍历
              的过程中，一次排序都没有说明整个链表已经
              达到增序的要求
            */
            int flag = 0;
            while (comparedNode.next != null) {
                if (comparedNode.val > comparedNode.next.val) {
                    int temp = comparedNode.next.val;
                    comparedNode.next.val = comparedNode.val;
                    comparedNode.val = temp;
                    flag++;
                }
                comparedNode = comparedNode.next;
            }
            if (flag == 0) {
                break;
            }
        }
        return head;
    }
}

2. 归并算法
   上面这种方式可以算作一种暴力解法，直接遍历，另外一种方式是采用归并算法来解。什么是归并算法呢？
   以4->2->1->3->5为例：我们先将整个链表打散，并两两分成一组，如果存在单个的就自成一组，这样一来，在每个组内，我们就是进行一对一的比较，是很容易的。

   
   归
   

   在组内进行大小比较后，形成组内的链表，我们可以看到，每一个链表都是由小到大排序的：

   
   组内排序
   在这之后，我们那再将排序从两个节点，扩大到两个组进行排序（其实节点也就是最小单位的组），这时候我们发现，只需要比较两个组最左边的元素，就可以判断哪一个节点是这两个组中最小的一个，往复的这样比较就可以将两个组合并，并获得递增链表：
   并
   这样一来虚拟节点的next不就是我们有序组的头节点吗！，不停的归并下去，直到所有组归并完成。

public class Solution2 {
    public ListNode sortList(ListNode head) {
        return head == null ? head : mergeAndSort(head);
    }

    private ListNode mergeAndSort(ListNode head) {
        if (head.next == null) {
            return head;
        }

        ListNode slow = head;
        ListNode fast = head;
        ListNode origin = null;

        while (fast != null && fast.next != null) {
            origin = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        /*
        此时slow的为止为整个链表的中部
        现在将slow右边的部分断开，以slow为第一段的终点，
        slow.next作为第二段的起点，将链表一分为二
         */
        origin.next = null;
        ListNode left = mergeAndSort(head);
        ListNode right = mergeAndSort(slow);
        return merge(left, right);
    }

    private ListNode merge(ListNode left, ListNode right) {
        ListNode result = new ListNode(0);
        ListNode cursor = result;
        while (left != null && right != null) {
            if (left.val < right.val) {
                cursor.next = left;
                cursor = left;
                left = left.next;
            } else {
                cursor.next = right;
                cursor = right;
                right = right.next;
            }
        }
        if (left == null) {
            cursor.next = right;
        } else {
            cursor.next = left;
        }
        return result.next;
    }
}