CASE1 【思想】：利用一个map来存储每个节点在有序链表中的前驱节点，剩下的就直接暴力插排就行 时间复杂度O(n^2) 空间复杂度O(n)
class Solution { public ListNode insertionSortList(ListNode head) { if(head==null||head.next==null) return head; ListNode tempHead = new ListNode(Integer.MIN_VALUE); tempHead.next = head; ListNode curNode = head.next,rear = head; Map<ListNode,ListNode> map = new HashMap<>();//key:node value:pre map.put(head,tempHead);//更新head的前驱为tempHead head.next = null;//断链，否则会出现环。此时head节点单独构成一个有序链表。 //遍历剩下的无序链表中的节点 while(curNode!=null){ ListNode next = curNode.next; if(rear.val<=curNode.val){ map.put(curNode,rear);//更新curNode的前驱为rear curNode.next = null; rear.next = curNode; rear = rear.next; }else{ ListNode temp = rear; while(temp!=tempHead&&temp.val>=curNode.val){ temp = map.get(temp); } /*因为在有序链表中插入curNode后，其后继节点的前驱变更为了curNode， 所以这里不但要更新curNode的前驱，还要更新在有序链表中插入curNode后, 其后继节点的前驱为curNode*/ map.put(curNode,temp); map.put(temp.next,curNode); //在有序链表中插入curNode curNode.next = temp.next; temp.next = curNode; } curNode = next; } return tempHead.next; } }case2: 【思想】：反过来思考，当找到一个无序节点时，从有序链表的队头开始匹配，找到一个合适的插入位置将其插入 时间复杂度O(N^2),空间复杂度O(1)
class Solution { public ListNode insertionSortList(ListNode head) { if(head==null||head.next==null) return head; ListNode tempHead = new ListNode(Integer.MIN_VALUE); tempHead.next = head; //rear指向当前有序链表的最后一个节点,curNode指向未遍历的节点 ListNode rear = head,curNode = head.next; rear.next = null;//断链，保证rear指向的是我们找到的最后一个符合条件的节点 while(curNode!=null){ ListNode next = curNode.next; if(rear.val<=curNode.val){ rear.next = curNode; rear = rear.next; rear.next = null; }else{ /*pre指向虚拟头节点，因为这样直接既保证pre.next指向的一定是原链表中的节点 而且这样还可以保证循环终止后pre指向的节点是有序链表中最后一个小于curNode的节点， 其下一个位置即为要将curNode插入的位置*/ ListNode pre = tempHead; while(pre.next.val<curNode.val){ pre = pre.next; } curNode.next = pre.next; pre.next = curNode; } curNode = next; } return tempHead.next; } }