题目：
1、Sort a linked list using insertion sort
2、Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
3、Sort a linked list in O(n log n) time using constant space complexity
LeetCode上的三道题，汇总在一块。自认为这三道题有层层递进的关系。
1、首先第一个，按插入法进行排序，比较简单，但是不同于数组的插入排序，为什么？因为链表的插入需要O(1)，而数组需要O(n)。
代码如下：
public ListNode insertionSortList(ListNode head) {
ListNode newHead = new ListNode(0);
ListNode pNode = head;
while (pNode != null) {
ListNode node = newHead;
while (node.next != null) {
if (node.next.val > pNode.val)
break;
node = node.next;
}
ListNode temp = pNode.next;
pNode.next = node.next;
node.next = pNode;
pNode = temp;
}
return newHead.next;
}在代码第一行中加入了一个头节点，这样更有利于插入操作的统一性，不用另外考虑头节点。接下来就是遍历整个链表，找到合适的位置，进行插入！
2、第二个的问题也比较简单，可以参看数组的归并，代码如下：
private ListNode mergeTwoLists(ListNode head1, ListNode head2) {
ListNode head = new ListNode(0);
ListNode root = head;
while (head1 != null && head2 != null) {
if (head1.val < head2.val) {
head.next = head1;
head1 = head1.next;
} else {
head.next = head2;
head2 = head2.next;
}
head = head.next;
}
if (head1 != null) {
head.next = head1;
}
if (head2 != null) {
head.next = head2;
}
return root.next;
}3、有了上面两个题做基础，第三个就非常好解答了。首先用插入排序肯定不行，因为他的时间复杂度是O(n^2)。联系到第二道题，就可以联想到归并排序，对，就是这个思路：
代码如下：
public ListNode sortList(ListNode head) {
if (head == null) {
return head;
}
int len = 0;
ListNode node = head;
while (node != null) {
len++;
node = node.next;
}
if (len == 1) {
return head;
}
node = head;
for (int i = 0; i < (len/2)-1; i++) {
node = node.next;
}
ListNode midNode = node.next;
node.next = null;
head = sortList(head);
midNode = sortList(midNode);
return mergeTwoLists(head, midNode);
}
private ListNode mergeTwoLists(ListNode head1, ListNode head2) {
ListNode head = new ListNode(0);
ListNode root = head;
while (head1 != null && head2 != null) {
if (head1.val < head2.val) {
head.next = head1;
head1 = head1.next;
} else {
head.next = head2;
head2 = head2.next;
}
head = head.next;
}
if (head1 != null) {
head.next = head1;
}
if (head2 != null) {
head.next = head2;
}
return root.next;
}完全是归并排序的模式，但是对于上面取中间节点比较繁琐，有另外一个办法，只需要遍历一次链表：两个指针p1,p2同时从head开始，p1每次next一次，即p1 = p1.next;但是p2每次next两次，即p2
= p2.next.next;
显然，当p2到达未端时，就可以认为p1指向的是中间节点！！！
LeetCode-Sort List,链表排序(插入和归并)，时间复杂度O(n^2) and O(nlgn)
原文：http://blog.csdn.net/my_jobs/article/details/43988745