单向链表插入排序 Java

游动指针h ； 待插入节点指针pt

节点插入关键：h.next = pt; 不可能是h = pt, 链到指针的末尾没用呀，要链到节点末尾

默认无头结点，无头结点的思路：

三种可能

1. 比较头部

2. 循环比较中间

3. 追加末尾

为何比较头节点：因为循环中间部分的时候没有比较头节点

while (h.next != null) { //比较有序部分

整体代码：

package linkedList;

/**
 * Definition for singly-linked list. 
 * public class ListNode 
 * { 
 *     int val; 
 *     ListNode next;
 *     ListNode(int x) { 
 *           val = x; 
 *           next = null;
 *     } 
 * }
 * @
 */
public class Solution {
	
	public ListNode insertionSortList(ListNode head) {
		if (head == null || head.next == null)
			return head;

		ListNode c = head.next;  //未排序游动指针C
		head.next = null;  
		ListNode pt, h;   //pt:临时节点指针，h：已排序部分游动指针

		while (c != null) {

			pt = c;
			c = c.next;
			pt.next = null;

			if (head.val > pt.val) { //比较头部
				pt.next = head;
				head = pt;
				continue;
			}

			h = head;
			while (h.next != null) { //比较有序部分
				if (h.next.val > pt.val) {
					pt.next = h.next;
					h.next = pt;
					break;
				}

				h = h.next;
			}

			if (h.next == null) { //追加末尾
				h.next = pt;
			}
		}

		return head;
	}
}