Heading

147.对链表进行插入排序 (opens new window)

Tags: algorithms linked-list sort

Langs: c cpp csharp golang java javascript kotlin php python python3 ruby rust scala swift typescript

• algorithms
• Medium (65.36%)
• Likes: 231
• Dislikes: -
• Total Accepted: 44.3K
• Total Submissions: 67.7K
• Testcase Example: '[4,2,1,3]'

对链表进行插入排序。

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

 

插入排序算法：

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

 

示例 1：

输入: 4->2->1->3
输出: 1->2->3->4

示例 2：

输入: -1->5->3->4->0
输出: -1->0->3->4->5

/*
 * @lc app=leetcode.cn id=147 lang=javascript
 *
 * [147] 对链表进行插入排序
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var insertionSortList = function (head) {
    const hair = new ListNode();
    hair.next = head;
    let p = head, q = p ? p.next : null;

    while (q) {
        let r = hair;
        while (r.next && q.val > r.next.val) {
            r = r.next
        }
        if (q !== r.next) {//插入r后面
            p.next = q.next
            q.next = r.next
            r.next = q
        } else {
            p = p.next
        }
        q = p.next
    }
    return hair.next;
};
// @lc code=end