商城网站设计制作,中小企业网站建设 网络营销,香水网站模板,工商网上核名系统题目#xff1a;
给定链表的头节点head,每K个节点一组进行翻转#xff0c;返回修改后的链表。
K是正整数#xff0c;它的值小于等于链表的长度#xff0c;如果节点总数不是K的整数组#xff0c;那么将最后剩余的节点保持原有顺序。不能只改变节点内容的值#xff0c;需…题目
给定链表的头节点head,每K个节点一组进行翻转返回修改后的链表。
K是正整数它的值小于等于链表的长度如果节点总数不是K的整数组那么将最后剩余的节点保持原有顺序。不能只改变节点内容的值需要进行实际的节点交换。 输入head [1,2,3,4,5], k 2
输出[2,1,4,3,5] 需要把链表节点按照 k 个一组分组所以可以使用一个指针 head 依次指向每组的头节点。这个指针每次向前移动 k 步直至链表结尾对于每个分组我们先判断它的长度是否大于等于 k。若是我们就翻转这部分链表否则不需要翻转。
接下来的问题就是如何翻转一个分组内的子链表
翻转一个链表并不难过程可以参考「206. 反转链表」。但是对于一个子链表除了翻转其本身之外还需要将子链表的头部与上一个子链表连接以及子链表的尾部与下一个子链表连接。 在翻转子链表的时候我们不仅需要子链表头节点 head还需要有 head 的上一个节点 pre以便翻转完后把子链表再接回 pre。
对于第一个子链表它的头节点 head 前面是没有节点 pre 的们新建一个节点把它接到链表的头部让它作为 pre 的初始值这样 head 前面就有了一个节点我们就可以避开链表头部的边界条件。
反复移动指针 head 与 pre对 head 所指向的子链表进行翻转直到结尾。 # Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution(object):def reverseKGroup(self, head, k)::type head: Optional[ListNode]:type k: int:rtype: Optional[ListNode]n0 #n 用来记录链表的总节点数curhead #是当前指向链表的指针从头节点开始遍历while cur:n1curcur.next pdummyListNode(nexthead) #虚拟的头节点,指向原链表的头节点#p 是用来保持链表头部的指针在每次反转一组节点后用它来调整前一个分组的 next 指针preNone #用来指向当前反转过程中的前一个节点curhead #指向链表的第一个节点作为反转操作的当前节点while nk: #只有当剩余的节点数大于或等于 k 时才进行反转操作n-k #表示已经反转了一个大小为 k 的节点组所以剩余的节点数减少了 kfor _ in range(k): #反转当前组的 k 个节点nxtcur.next #保存当前节点的下一个节点cur.nextpre #将当前节点的 next 指向前一个节点实现反转操作precur # 将 pre 指向当前节点作为下一个节点的前驱curnxt #将 cur 移动到下一个节点继续进行反转tailp.next #获取当前节点组反转后的尾节点tail.nextcur#将反转后的组尾节点的 next 指向当前的 cur即未反转部分的开始p.nextpre #将p的 next 指向反转后的第一个节点这样前一个部分和当前部分就连接在一起ptail #更新 p0 为反转后的组的尾节点以便处理下一个组return dummy.next
时间复杂度O(N)
空间复杂度O(1) 源自力扣官方题解
