147. Insertion Sort List
給定一個單鏈表的頭節點，使用插入排序法對鏈表進行排序，並返回排序後鏈表的頭節點。
插入排序算法的步驟：插入排序迭代地進行，每次消耗一個輸入元素，並生成一個已排序的輸出列表。
在每次迭代中，插入排序從輸入數據中移除一個元素，找到它在已排序列表中的位置，並將其插入該位置。
重複此過程直到沒有輸入元素剩餘。
以下是插入排序算法的圖形示例。部分已排序的列表（黑色）最初僅包含列表中的第一個元素。每次迭代中，一個元素（紅色）從輸入數據中移除，並就地插入到已排序列表中。
範例 :
輸入: head = [4,2,1,3]
Python
from typing import Optional
# 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: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
dummy = ListNode(0) # Create a dummy node as the new head of the sorted list
dummy.next = head
curr = head.next # The current node to be sorted
head.next = None # Initialize the sorted list with the first node
while curr:
prev = dummy # Start from the dummy node each time
next_temp = curr.next # Save the next node to be processed
# Find the correct position to insert the current node
while prev.next and prev.next.val < curr.val:
prev = prev.next
# Insert the current node in the sorted list
curr.next = prev.next
prev.next = curr
# Move to the next node to be sorted
curr = next_temp
return dummy.next
18.51MB, 399ms
C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
if (!head || !head->next) {
return head;
}
ListNode* dummy = new ListNode(0); // Create a dummy node as the new head of the sorted list
ListNode* curr = head; // The current node to be sorted
while (curr) {
ListNode* prev = dummy; // Start from the dummy node each time
ListNode* next = curr->next; // Save the next node to be processed
// Find the correct position to insert the current node
while (prev->next && prev->next->val < curr->val) {
prev = prev->next;
}
// Insert the current node in the sorted list
curr->next = prev->next;
prev->next = curr;
// Move to the next node to be sorted
curr = next;
}
ListNode* sortedHead = dummy->next;
delete dummy; // Free the dummy node
return sortedHead;
}
};
13.06MB, 38ms
Javascript
/**
* 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;
}
const dummy = new ListNode(0); // Create a dummy node as the new head of the sorted list
let curr = head; // The current node to be sorted
while (curr !== null) {
let prev = dummy; // Start from the dummy node each time
let next = curr.next; // Save the next node to be processed
// Find the correct position to insert the current node
while (prev.next !== null && prev.next.val < curr.val) {
prev = prev.next;
}
// Insert the current node in the sorted list
curr.next = prev.next;
prev.next = curr;
// Move to the next node to be sorted
curr = next;
}
return dummy.next;
};
52.25MB, 95ms
