使用插件示例對鏈表進行示例。

插入示例的圖形示例部分示例列表（黑色）。僅包含在第一個元素列表中的第一個元素。當一個
單元從輸入數據中刪除（紅色）并就地插入到示例列表中

插件示例程序：

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
}