LeetCode对链表进行插入排序

对链表进行插入排序

题目描述:对链表进行插入排序。

插入排序的动画演示如上。从第一个元素开始,该链表可以被认为已经部分排序(用黑色表示)。 每次迭代时,从输入数据中移除一个元素(用红色表示),并原地将其插入到已排好序的链表中。

插入排序算法:

  • 插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。
  • 每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。
  • 重复直到所有输入数据插入完为止。

示例说明请见LeetCode官网。

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/insertion-sort-list/

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法一:链表遍历

  • 首先,如果链表为空或者链表只有一个节点,则不用排序,直接返回。
  • 否则,使用插入排序的方式将链表中的节点都放到一个List中nodes;
  • 然后,按照nodes的顺序重新构造一个新的链表即为排序后的链表,返回之。

import com.kaesar.leetcode.ListNode;import java.util.ArrayList;import java.util.List;public class LeetCode_147 { public static ListNode insertionSortList(ListNode head) { // 如果链表为空或者链表只有一个节点,则不用排序,直接返回 if (head == null || head.next == null) { return head; } List nodes = new ArrayList(); nodes.add(head); ListNode cur = head.next; while (cur != null) { int i = nodes.size() – 1; for (; i >= 0; i–) { if (nodes.get(i).val < cur.val) { break; } } nodes.add(i + 1, cur); cur = cur.next; } ListNode newHead = nodes.get(0); cur = newHead; for (int i = 1; i < nodes.size(); i++) { cur.next = nodes.get(i); cur = cur.next; } cur.next = null; return newHead; } public static void main(String[] args) { ListNode head = new ListNode(4); head.next = new ListNode(2); head.next.next = new ListNode(1); head.next.next.next = new ListNode(3); System.out.println("排序之前"); ListNode cur = head; while (cur != null) { System.out.print(cur.val + " "); cur = cur.next; } System.out.println(); System.out.println("排序之后"); ListNode newHead = insertionSortList(head); cur = newHead; while (cur != null) { System.out.print(cur.val + " "); cur = cur.next; } }}

【每日寄语】 每个人的人生轨迹恐怕都是事先命定的,但是你得努力,并相信命运是掌握在自己手中的,人不怕有理想,不怕这个理想有多高多远多大,只要坚持,不过分高估自己,总会成功。

郑重声明:本文内容及图片均整理自互联网,不代表本站立场,版权归原作者所有,如有侵权请联系管理员(admin#wlmqw.com)删除。
(0)
用户投稿
上一篇 2022年6月30日
下一篇 2022年6月30日

相关推荐

联系我们

联系邮箱:admin#wlmqw.com
工作时间:周一至周五,10:30-18:30,节假日休息