leetCode-147:Insertion Sort List

问题描述

给定一个链表，要求用插入排序的方式对链表进行升序排序。题目链接：**点我**

样例输入输出

输入：4->2->1->3

输出：1->2->3->4

输入：-1->5->3->4->0

输出：-1->0->3->4->5

问题解法

直接使用插入排序的算法进行排序。代码如下

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution
{
    public ListNode insertionSortList(ListNode head)
    {
        if (head == null)
        {
            return head;
        }
        
        ListNode dummy = new ListNode(Integer.MIN_VALUE, head);
        ListNode p = head;
        while (p.next != null)
        {
            ListNode current = p.next;
            ListNode q = dummy;
            boolean isMove = true;
            while (q.next != current)
            {
                if (q.next.val < current.val)
                {
                    q = q.next;
                }
                else
                {
                    p.next = current.next;
                    current.next =q.next;
                    q.next = current;
                    isMove = false;
                    break;
                }
            }
            
            if (isMove)
            {
                p = p.next;
            }
        }
        return dummy.next;
    }
}