首页 > 代码库 > [leetcode] Insertion Sort List
[leetcode] Insertion Sort List
Sort a linked list using insertion sort.
https://oj.leetcode.com/problems/insertion-sort-list/
思路：模拟插入排序，因为没有pre的指针，所以找位置是从前向后找的。
public class Solution { public ListNode insertionSortList(ListNode head) { if (head == null || head.next == null) return head; ListNode newHead = new ListNode(-1); newHead.next = head; ListNode cur = head.next; ListNode pre = head; while (cur != null) { ListNode next = cur.next; ListNode p = newHead; while (p.next != null && p.next.val < cur.val) p = p.next; pre.next = next; cur.next = p.next; p.next = cur; if (p == pre) pre = pre.next; cur = next; } return newHead.next; } public static void main(String[] args) { ListNode head = ListUtils.makeList(new int[] { 1, 3, 5, 6, 4 }); ListUtils.printList(head); head = new Solution().insertionSortList(head); ListUtils.printList(head); }}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。