上次编辑到这里，代码来自缓存 点击恢复默认模板
/**
* 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* sortList(ListNode* head) {
}
};
golang 解法, 执行用时: 24 ms, 内存消耗: 7.1 MB, 提交时间: 2022-11-21 09:56:19
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func merge(head1, head2 *ListNode) *ListNode {
dummyHead := &ListNode{}
temp, temp1, temp2 := dummyHead, head1, head2
for temp1 != nil && temp2 != nil {
if temp1.Val <= temp2.Val {
temp.Next = temp1
temp1 = temp1.Next
} else {
temp.Next = temp2
temp2 = temp2.Next
}
temp = temp.Next
}
if temp1 != nil {
temp.Next = temp1
} else if temp2 != nil {
temp.Next = temp2
}
return dummyHead.Next
}
func sort(head, tail *ListNode) *ListNode {
if head == nil {
return head
}
if head.Next == tail {
head.Next = nil
return head
}
slow, fast := head, head
for fast != tail {
slow = slow.Next
fast = fast.Next
if fast != tail {
fast = fast.Next
}
}
mid := slow
return merge(sort(head, mid), sort(mid, tail))
}
func sortList(head *ListNode) *ListNode {
return sort(head, nil)
}
golang 解法, 执行用时: 32 ms, 内存消耗: 7 MB, 提交时间: 2022-11-21 09:55:46
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func merge(head1, head2 *ListNode) *ListNode {
dummyHead := &ListNode{}
temp, temp1, temp2 := dummyHead, head1, head2
for temp1 != nil && temp2 != nil {
if temp1.Val <= temp2.Val {
temp.Next = temp1
temp1 = temp1.Next
} else {
temp.Next = temp2
temp2 = temp2.Next
}
temp = temp.Next
}
if temp1 != nil {
temp.Next = temp1
} else if temp2 != nil {
temp.Next = temp2
}
return dummyHead.Next
}
func sortList(head *ListNode) *ListNode {
if head == nil {
return head
}
length := 0
for node := head; node != nil; node = node.Next {
length++
}
dummyHead := &ListNode{Next: head}
for subLength := 1; subLength < length; subLength <<= 1 {
prev, cur := dummyHead, dummyHead.Next
for cur != nil {
head1 := cur
for i := 1; i < subLength && cur.Next != nil; i++ {
cur = cur.Next
}
head2 := cur.Next
cur.Next = nil
cur = head2
for i := 1; i < subLength && cur != nil && cur.Next != nil; i++ {
cur = cur.Next
}
var next *ListNode
if cur != nil {
next = cur.Next
cur.Next = nil
}
prev.Next = merge(head1, head2)
for prev.Next != nil {
prev = prev.Next
}
cur = next
}
}
return dummyHead.Next
}
python3 解法, 执行用时: 460 ms, 内存消耗: 30.4 MB, 提交时间: 2022-11-21 09:55:22
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
'''
自底向上归并排序
'''
class Solution:
def sortList(self, head: ListNode) -> ListNode:
def merge(head1: ListNode, head2: ListNode) -> ListNode:
dummyHead = ListNode(0)
temp, temp1, temp2 = dummyHead, head1, head2
while temp1 and temp2:
if temp1.val <= temp2.val:
temp.next = temp1
temp1 = temp1.next
else:
temp.next = temp2
temp2 = temp2.next
temp = temp.next
if temp1:
temp.next = temp1
elif temp2:
temp.next = temp2
return dummyHead.next
if not head:
return head
length = 0
node = head
while node:
length += 1
node = node.next
dummyHead = ListNode(0, head)
subLength = 1
while subLength < length:
prev, curr = dummyHead, dummyHead.next
while curr:
head1 = curr
for i in range(1, subLength):
if curr.next:
curr = curr.next
else:
break
head2 = curr.next
curr.next = None
curr = head2
for i in range(1, subLength):
if curr and curr.next:
curr = curr.next
else:
break
succ = None
if curr:
succ = curr.next
curr.next = None
merged = merge(head1, head2)
prev.next = merged
while prev.next:
prev = prev.next
curr = succ
subLength <<= 1
return dummyHead.next
python3 解法, 执行用时: 356 ms, 内存消耗: 30.4 MB, 提交时间: 2022-11-21 09:54:41
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
'''
自顶向下归并排序
'''
class Solution:
def sortList(self, head: ListNode) -> ListNode:
def sortFunc(head: ListNode, tail: ListNode) -> ListNode:
if not head:
return head
if head.next == tail:
head.next = None
return head
slow = fast = head
while fast != tail:
slow = slow.next
fast = fast.next
if fast != tail:
fast = fast.next
mid = slow
return merge(sortFunc(head, mid), sortFunc(mid, tail))
def merge(head1: ListNode, head2: ListNode) -> ListNode:
dummyHead = ListNode(0)
temp, temp1, temp2 = dummyHead, head1, head2
while temp1 and temp2:
if temp1.val <= temp2.val:
temp.next = temp1
temp1 = temp1.next
else:
temp.next = temp2
temp2 = temp2.next
temp = temp.next
if temp1:
temp.next = temp1
elif temp2:
temp.next = temp2
return dummyHead.next
return sortFunc(head, None)
