使用插件示例對(duì)鏈表進(jìn)行示例。

插入示例的圖形示例部分示例列表（黑色）。僅包含在第一個(gè)元素列表中的第一個(gè)元素。當(dāng)一個(gè)
單元從輸入數(shù)據(jù)中刪除（紅色）并就地插入到示例列表中

插件示例程序：

1. 插入示例示例，每次重復(fù)使用一個(gè)輸入元素，并增加一個(gè)示例的輸出列表。
2. 有時(shí)在中，插入示例輸入數(shù)據(jù)中的一個(gè)元素，在示例列表中找到它的舊位置，然后將其刪除到那里。
3. 它重復(fù)直到?jīng)]有輸入元素。

示例 1：

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

示例 2：

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

題意

對(duì)給定的鏈表進(jìn)行插件示例。

思路

遍歷原鏈表，每次將當(dāng)前結(jié)點(diǎn)從原鏈表中下載，到新鏈表的位置表即可。

代碼實(shí)現(xiàn)

爪哇

class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        
        while (head != null) {
            // 將每一個(gè)原結(jié)點(diǎn)斷開(kāi)并取出
            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
}