题解 | #链表的插入排序#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     *  需要使用插入排序，
	   1.创建头节点为虚节点，将虚节点指针指向原头节点
	   2.循环  从原头节点第二个node开始 往前 判断，是否存在比该节点大得数据，存在则交换指针，
	   3.每循环一次，都需要将记录下次需要遍历node得引用，
     * @param head ListNode类
     * @return ListNode类
     */
  public ListNode insertionSortList (ListNode head) {
        if(head==null||head.next==null)return head;
	//创建头节点
        ListNode tempNode =new ListNode(0);
	//连接指针
        tempNode.next=head;
	//从第二个节点开始遍历是否需要插入
        ListNode current =head.next;
	//设置引用对象，交换指针得时候需要有  3个节点得指针变动，
	//pre节点得next指向currentNode，
	//currentNode得上一节点得next需要指向currentNode得next
	//currentNode得next指向pre节点得next
	//如果需要指针变动，则会把当前节点插入到前面，所以currentLast指针不用变动，
	//如果不需要指针变动，则下次循环得时候currentLast指针为currentLast得next节点
        ListNode next,pre,currentLast=head;
        while (true){
            pre=tempNode;
            if(current==null)break;
            next=current.next;
            while (pre.next.val<current.val){
                pre=pre.next;
            }
            if(pre.next!=current){
                //交换  1,2,3,4,
                currentLast.next = next;
                current.next =pre.next;
                pre.next = current;
            }else{
                currentLast = current;
            }
            current=next;
        }
        return tempNode.next;
    }
}