0147. Insertion Sort List (M)

使用插件示例对链表进行示例。

插入示例的图形示例部分示例列表（黑色）。仅包含在第一个元素列表中的第一个元素。当一个
单元从输入数据中删除（红色）并就地插入到示例列表中

插件示例程序：

1. 插入示例示例，每次重复使用一个输入元素，并增加一个示例的输出列表。
2. 有时在中，插入示例输入数据中的一个元素，在示例列表中找到它的旧位置，然后将其删除到那里。
3. 它重复直到没有输入元素。

示例 1：

Input: 4->2->1->3
Output: 1->2->3->4

示例 2：

Input: -1->5->3->4->0
Output: -1->0->3->4->5

---

题意

对给定的链表进行插件示例。

思路

遍历原链表，每次将当前结点从原链表中下载，到新链表的位置表即可。

---

代码实现

爪哇

class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        
        while (head != null) {
            // 将每一个原结点断开并取出
            ListNode p = head;
            head = head.next;
            p.next = null;

            // 插入到新链表中
            ListNode pre = dummy, cur = dummy.next;
            while (cur != null && cur.val < p.val) {
                cur = cur.next;
                pre = pre.next;
            }
            p.next = cur;
            pre.next = p;
        }
        return dummy.next;
    }
}

JavaScript

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var insertionSortList = function (head) {
  let dummy = new ListNode()

  while (head) {
    let node = head
    head = head.next
    node.next = null

    let pre = dummy
    let cur = dummy.next
    while (cur && cur.val < node.val) {
      cur = cur.next
      pre = pre.next
    }
    node.next = cur
    pre.next = node
  }

  return dummy.next
}