Question

147. 对链表进行插入排序

English Version

题目描述

给定单个链表的头

 head ，使用 插入排序 对链表进行排序，并返回 _排序后链表的头_ 。

插入排序 算法的步骤:

1. 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
2. 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
3. 重复直到所有输入数据插入完为止。

下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。

对链表进行插入排序。

 

示例 1：

输入: head = [4,2,1,3]
输出: [1,2,3,4]

示例 2：

输入: head = [-1,5,3,4,0]
输出: [-1,0,3,4,5]

 

提示：

• 列表中的节点数在 [1, 5000]范围内
• -5000 <= Node.val <= 5000

解法

方法一

# Definition for singly-linked list.
# class ListNode:
#   def __init__(self, val=0, next=None):
#     self.val = val
#     self.next = next
class Solution:
  def insertionSortList(self, head: ListNode) -> ListNode:
    if head is None or head.next is None:
      return head
    dummy = ListNode(head.val, head)
    pre, cur = dummy, head
    while cur:
      if pre.val <= cur.val:
        pre, cur = cur, cur.next
        continue
      p = dummy
      while p.next.val <= cur.val:
        p = p.next
      t = cur.next
      cur.next = p.next
      p.next = cur
      pre.next = t
      cur = t
    return dummy.next

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *   int val;
 *   ListNode next;
 *   ListNode() {}
 *   ListNode(int val) { this.val = val; }
 *   ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
  public ListNode insertionSortList(ListNode head) {
    if (head == null || head.next == null) {
      return head;
    }
    ListNode dummy = new ListNode(head.val, head);
    ListNode pre = dummy, cur = head;
    while (cur != null) {
      if (pre.val <= cur.val) {
        pre = cur;
        cur = cur.next;
        continue;
      }
      ListNode p = dummy;
      while (p.next.val <= cur.val) {
        p = p.next;
      }
      ListNode t = cur.next;
      cur.next = p.next;
      p.next = cur;
      pre.next = t;
      cur = t;
    }
    return dummy.next;
  }
}

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *   this.val = (val===undefined ? 0 : val)
 *   this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var insertionSortList = function (head) {
  if (head == null || head.next == null) return head;
  let dummy = new ListNode(head.val, head);
  let prev = dummy,
    cur = head;
  while (cur != null) {
    if (prev.val <= cur.val) {
      prev = cur;
      cur = cur.next;
      continue;
    }
    let p = dummy;
    while (p.next.val <= cur.val) {
      p = p.next;
    }
    let t = cur.next;
    cur.next = p.next;
    p.next = cur;
    prev.next = t;
    cur = t;
  }
  return dummy.next;
};