Sort a linked list using insertion sort.

public class Solution {     public ListNode insertionSortList(ListNode head) {           ListNode root = new ListNode(0); // 头结点         root.next = head;         ListNode p = head;         ListNode q;         ListNode r; //例如6->4->3->7->1->2         while (p != null && p.next != null) {             if (p.val <= p.next.val) {//如果此时p等于3,3<7,符合升序，p就指向7                 p = p.next;             }else { //例如6大于4，则把4和6互换，另q等于4，所以6就指向了3(q.next)                 q = p.next;                 p.next = q.next;                                  r = root;                                                 while (r.next.val <= q.val) { //此时r.next是6,6大于4，不执行循环                     r = r.next;//最后进行到0->1->3->4->6->7->2，p等于7，q等于2，则7指向null(q.next)，此时1小于2(r.next.val < q.val)，所以另r等于1，再往下走，则让2->3, 1->2                 }                   q.next = r.next; //使得4指向6                 r.next = q; //root指向4，完成4->6->3             }         }           return root.next;     } }
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。