上次编辑到这里，代码来自缓存 点击恢复默认模板
/**
* 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) {
}
};
golang 解法, 执行用时: 4 ms, 内存消耗: 3.1 MB, 提交时间: 2022-11-24 11:10:23
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func insertionSortList(head *ListNode) *ListNode {
if head == nil {
return nil
}
dummyHead := &ListNode{Next: head}
lastSorted, curr := head, head.Next
for curr != nil {
if lastSorted.Val <= curr.Val {
lastSorted = lastSorted.Next
} else {
prev := dummyHead
for prev.Next.Val <= curr.Val {
prev = prev.Next
}
lastSorted.Next = curr.Next
curr.Next = prev.Next
prev.Next = curr
}
curr = lastSorted.Next
}
return dummyHead.Next
}
python3 解法, 执行用时: 176 ms, 内存消耗: 16.9 MB, 提交时间: 2022-11-24 11:09:56
# 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 not head:
return head
dummyHead = ListNode(0)
dummyHead.next = head
lastSorted = head
curr = head.next
while curr:
if lastSorted.val <= curr.val:
lastSorted = lastSorted.next
else:
prev = dummyHead
while prev.next.val <= curr.val:
prev = prev.next
lastSorted.next = curr.next
curr.next = prev.next
prev.next = curr
curr = lastSorted.next
return dummyHead.next
