[牛客经典必刷算法题] LC5-链表的插入排序

[牛客经典必刷算法题] LC5-链表的插入排序

• • 题目描述
  • 示例
  • 思路
  • 解答

本题链接

题目描述

使用插入排序对链表进行排序。

示例

输入
{30,20,40}返回值
{20,30,40}

思路

通过虚拟头节点处理链表排序

插入排序算法描述：

• 步骤一：从第一个元素开始，该元素可以认为已经被排序；
• 步骤二：取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 步骤三：如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 步骤四：重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 步骤五：将新元素插入到该位置后；
• 步骤六：重复步骤二～五

解答

import java.util.*;/** public class ListNode {*   int val;*   ListNode next = null;* }*/public class Solution {/*** * @param head ListNode类 * @return ListNode类*/public ListNode insertionSortList (ListNode head) {if(head == null || head.next == null) return head;// 虚节点ListNode dummy = new ListNode(-1), pre;dummy.next = head;while(head != null && head.next != null){// 如果小于下一节点，直接跳过，加速排序if(head.val <= head.next.val){head = head.next;continue;}// 寻找当前节点正确位置pre = dummy;while(pre.next.val < head.next.val) pre = pre.next;// 取出当前节点currListNode curr = head.next;//保存下一节点head.next = curr.next;// 插入操作curr.next = pre.next;pre.next = curr;}return dummy.next;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！