题解 | #输出单向链表中倒数第k个结点#

提供一个空间复杂度为O（1）的解法：插入排序。初始条件下，把链表的头节点摘下放在另外一个链表中，然后每次取未排序链表的头部，进行链表合并即可。时间复杂度和数组中的插入排序一致。

public class Solution {
    public ListNode sortInList (ListNode head) {
        if(head==null||head.next==null)return head;
        ListNode res = head;
        ListNode cur  = head.next;
        res.next = null;
        while(cur!=null){
            ListNode p = cur;
            cur = cur.next;
            p.next = null;
            res = merge(res,p);
        }
        return res;
    }
    public ListNode merge(ListNode l1,ListNode l2){
        if(l1==null)return l2;
        if(l2==null)return l1;
        if(l1.val<l2.val){
            l1.next = merge(l1.next,l2);
            return l1;
        }
        else {
            l2.next = merge(l2.next,l1);
            return l2;
        }
    }
}