LeetCode-147-对链表进行插入排序 LeetCode-147-对链表进行插入排序

对链表进行插入排序

题目描述：对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
插入排序算法：

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。

每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。

重复直到所有输入数据插入完为止。

示例说明请见LeetCode官网。
【LeetCode-147-对链表进行插入排序】来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：链表遍历

首先，如果链表为空或者链表只有一个节点，则不用排序，直接返回。

否则，使用插入排序的方式将链表中的节点都放到一个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; } } }