Sort a linked list using insertion sort.

约定不等于承诺〃 2022-05-26 02:53 171阅读 0赞

> 题录：

> 分析如下：

使用插入排序的方法，对一个链表进行排序。  
插入排序的思想：第i个元素插入到已排序的前i-1个元素中。  
*注意*  
1 排好序的新链表和旧链表要断开。  
2 什么叫做插入排序，从A\[1\]到A\[n\]，依次把旧链表中的旧元素放入新链表的正确位置中，新链表是从没有元素开始逐渐排好序的，每加入一个旧元素，就把它放入正确的位置中。有三种可能的位置，新链表的表头，新链表的表中，新链表的表尾，因为在不同的位置会造成对head指针做不同的处理，所以需要分情况讨论。

/** * 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) {
            //链表为空，直接返回null
            if(head == null)
                return head;
            //旧链表从头结点的下一个结点开始遍历
            ListNode curr = head.next;
            //新链表中从含有一个元素开始，也就是旧链表的头结点
            ListNode newHead = head;
            //断开旧链表和新链表
            head.next = null;
    
            ListNode nCurr = head;
            while(curr != null){
                ListNode prev = null;
                //每次新插入结点，新链表从头结点开始遍历
                nCurr = head;
                //新链表没有遍历结束并且旧链表结点大于新链表的结点，新链表继续向后遍历
                while(nCurr != null && curr.val >= nCurr.val){
                    prev = nCurr;
                    nCurr = nCurr.next;
                }
                //记录当前要插入的旧链表中的结点
                ListNode p = curr;
                //旧链表中结点后移，即与要插入的结点断开
                curr = curr.next;
                p.next = nCurr;
                //新插入结点不是新链表头结点，则prev指针不为空，修改其next指向当前新插入的结点
                if(prev != null){
                    prev.next = p;
                }else{   //考虑如果插入的是新链表的头结点，则令head指向新结点
                    head = p;
                }
            }
            return head;
        }
    }