心得感受：

1、说实在的没有想到这个思路，链表毕竟不是数组，但是，通过这次的学习认识到了，链表也可以做所为的归并排序，很有意思。

2、写算法题，重在理解原理和思路，只要理解了，很多代码，敲起来就是得心应手的。比如下面的代码，你理解了是为了截断链表给sortInList 递归，你就自然，知道第一个要填head，第二个要填mid了！

// 上面所有的变量就是为了把链表分成三段
// 理解之后，代码敲起来就随心所欲
while(right!=null  && right.next !=null) {
    left = left.next;
    mid = mid.next;
    right = right.next.next;
}

// 断开左段链表的尾节点
left.next = null;

// 进行合并递归排序
return merge(sortInList(head), sortInList(mid));

3、关键是对过程和原理的理解，如果中途不到位，就要不断调试，确认自己的真知，比如下面的合并链表，并不要求要等长，以前理解是等长了。绝对不能一直半解一知，囫囵吞枣的。

/**
 * 合并链表，这里head1 和 head2 长度是可以不等长的，甚至相差好多个的。
 * 如果是不等长，while循环结束后，就将剩下链表headx的多个元素追加到合并链表尾部
 * 因为已经排序过了，所以，剩下的元素是可以直接追加到链表尾部到，构成有序链表
 */
ListNode merge(ListNode head1, ListNode head2) {
	//函数题
}

解题思路：

1、使用sortInList(ListNode head) 对链表进行分解成两段，传入merge函数里面；

2，函数里面嵌套 merge函数进行排序，最终合成一个最终的结果链表。

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }

        ListNode left = head;
        ListNode mid = head.next;
        ListNode right = head.next.next;

        // 上面所有的变量就是为了把链表分成三段
        // 理解之后，代码敲起来就随心所欲
        while(right!=null  && right.next !=null) {
            left = left.next;
            mid = mid.next;
            right = right.next.next;
        }

        // 断开左段链表的尾节点
        left.next = null;

        // 进行合并递归排序
        return merge(sortInList(head), sortInList(mid));
    }

    /**
     * 合并链表，这里head1 和 head2 长度是可以不等长的，甚至相差好多个的。
     * 如果是不等长，while循环结束后，就将剩下链表headx的多个元素追加到合并链表尾部
     * 因为已经排序过了，所以，剩下的元素是可以直接追加到链表尾部到，构成有序链表
     */
    ListNode merge(ListNode head1, ListNode head2) {
        // 定义新的链表头
        ListNode res = new ListNode(0);
        ListNode cur = res;

        //进行排序，注意指针下移
        while(head1!=null && head2!=null) {
            if(head1.val <= head2.val) {
                cur.next = head1;
                cur = cur.next;
                head1 = head1.next;
            } else {
                cur.next = head2;
                cur = cur.next;
                head2 = head2.next;
            }
        }

        //剩下还没有排序的直接追加到链表尾
        if(head1!=null) {
            cur.next = head1;
        } else {
            cur.next = head2;
        }

        return res.next;
    }
}