怎么创办个人网站,网站建设帐号,服务器哪些端口可以做网站,白云地网站建设题目#xff1a;
给定链表的头结点head,请将其按升序排列#xff0c;并返回排序后的链表 方法一#xff1a;自顶向下归并排序
链表自顶向下归并排序的过程#xff1a;
1.找到链表的中点#xff0c;以中点为分界#xff0c;将链表拆分成两个子链表。寻找链表的中点可以…题目
给定链表的头结点head,请将其按升序排列并返回排序后的链表 方法一自顶向下归并排序
链表自顶向下归并排序的过程
1.找到链表的中点以中点为分界将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法快指针每次移动 2 步慢指针每次移动 1 步当快指针到达链表末尾时慢指针指向的链表节点即为链表的中点
2.对两个链表进行排序
3.将两个排序后的子链表合并得到完整的排序后的链表。可以使用[合并两个有序链表]的做法将两个有序的子链表进行合并
可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 1即当链表为空或者链表只包含 1 个节点时不需要对链表进行拆分和排序 # Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution(object):def sortList(self, head)::type head: Optional[ListNode]:rtype: Optional[ListNode]def sortFunc(head,tail):#个递归的排序函数,tail 是递归调用时用于控制链表的尾部的边界if not head: #链表已经空return headif head.nexttail: #当前链表只有一个元素或者已经到达分割链表的边界head.nextNonereturn headslowfastheadwhile fast !tail:slowslow.nextfastfast.nextif fast ! tail: #fast 每次走两步slow 每次走一步fastfast.nextmidslow #当 fast 到达链表尾部时slow 就在链表的中间位置return merge(sortFunc(head,mid),sortFunc(mid,tail))
#递归调用sortFunc对head到mid的部分和mid到tail的部分分别进行排序然后将两个排序好的部分合并。合并的过程交给 merge 函数def merge(head1,head2): #将两个已排序的链表合并成一个有序的链表dummyHeadListNode(0) #虚拟的头节点temp,temp1,temp2dummyHead,head1,head2
#临时指针用来构建最终合并的链表,两个已排序链表的头节点while temp1 and temp2: #同时遍历temp1和temp2比较它们的值并将较小的节点连接到 temp 上直到其中一个链表遍历完if temp1.valtemp2.val:temp.nexttemp1 #将 temp1 加入合并后的链表temp1temp1.next #将 temp1 移动到下一个节点else:temp.nexttemp2temp2temp2.nexttemptemp.next #将已合并链表的指针后移if temp1: #如果 temp1 链表剩余节点未合并完则直接将剩余的节点连接temp.nexttemp1elif temp2: #如果 temp2 链表剩余节点未合并完同样将剩余的节点连接到temp.nexttemp2return dummyHead.next #去除虚拟结点返回合并后的链表的头节点return sortFunc(head,None) #sortList 函数通过调用 sortFunc 来对整个链表进行排序None 作为 tail 的参数表示没有上限
时间复杂度O(nlogn)
空间复杂度O(nlogn) 方法二自底向上归并排序
首先求得链表的长度 length然后将链表拆分成子链表进行合并。
具体做法 用 subLength 表示每次需要排序的子链表的长度初始时 subLength1。 每次将链表拆分成若干个长度为 subLength 的子链表最后一个子链表的长度可以小于 subLength按照每两个子链表一组进行合并合并后即可得到若干个长度为subLength×2 的有序子链表最后一个子链表的长度可以小于 subLength×2。合并两个子链表仍然使用[合并两个有序链表]的做法。 将 subLength 的值加倍重复第 2 步对更长的有序子链表进行合并操作直到有序子链表的长度大于或等于 length整个链表排序完毕。
举例
首先归并长度为 1 的子链表。例如 [4,2,1,3]把第一个节点和第二个节点归并第三个节点和第四个节点归并得到 [2,4,1,3]。 然后归并长度为 2 的子链表。例如 [2,4,1,3]把前两个节点和后两个节点归并得到 [1,2,3,4]。 然后归并长度为 4 的子链表。 依此类推直到归并的长度大于等于链表长度为止此时链表已经是有序的了。
初始链表: 4 - 2 - 1 - 3
step 1: - 分割: [4], [2], [1], [3] - 合并: [2 - 4], [1 - 3] - 结果: 2 - 4 - 1 - 3
step 2: - 分割: [2 - 4], [1 - 3] - 合并: [1 - 2 - 3 - 4] - 结果: 1 - 2 - 3 - 4
step 4: - 分割: [1 - 2 - 3 - 4] - 无需合并 - 结果: 1 - 2 - 3 - 4
最终结果: 1 - 2 - 3 - 4
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val0, nextNone):
# self.val val
# self.next nextclass Solution(object):# 获取链表长度def getListLength(self, head):length 0while head:length 1head head.nextreturn length# 分割链表# 如果链表长度 size不做任何操作返回空节点# 如果链表长度 size把链表的前 size 个节点分割出来断开连接并返回剩余链表的头节点def splitList(self, head, size):# 先找到 next_head 的前一个节点cur headfor _ in range(size - 1):if cur is None:breakcur cur.next# 如果链表长度 sizeif cur is None or cur.next is None:return None # 不做任何操作返回空节点next_head cur.nextcur.next None # 断开 next_head 的前一个节点和 next_head 的连接return next_head# 合并两个有序链表双指针# 返回合并后的链表的头节点和尾节点def mergeTwoLists(self, list1, list2):cur dummy ListNode() # 用哨兵节点简化代码逻辑while list1 and list2:if list1.val list2.val:cur.next list1 # 把 list1 加到新链表中list1 list1.nextelse: # 注相等的情况加哪个节点都是可以的cur.next list2 # 把 list2 加到新链表中list2 list2.nextcur cur.nextif list1:cur.nextlist1elif list2:cur.nextlist2while cur.next:curcur.nextreturn dummy.next, curdef sortList(self, head):length self.getListLength(head) # 获取链表长度dummy ListNode(nexthead) # 用哨兵节点简化代码逻辑step 1 # 步长参与合并的链表长度while step length:new_list_tail dummy # 新链表的末尾cur dummy.next # 每轮循环的起始节点while cur:# 从 cur 开始分割出两段长为 step 的链表头节点分别为 head1 和 head2head1 curhead2 self.splitList(head1, step)cur self.splitList(head2, step) # 下一轮循环的起始节点# 合并两段长为 step 的链表head, tail self.mergeTwoLists(head1, head2)# 合并后的头节点 head插到 new_list_tail 的后面new_list_tail.next headnew_list_tail tail # tail 现在是新链表的末尾step * 2return dummy.next时间复杂度O(logn)
空间复杂度O(1)
方法一的归并是自顶向下计算需要 O(logn) 的递归栈开销。
方法二将其改成自底向上计算空间复杂度优化成 O(1) 源自力扣官方题解灵茶山艾府
