{1,2,3,4,5},2{2,1,4,3,5}{},1{}
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param head ListNode类 # @param k int整型 # @return ListNode类 # class Solution: def reverseKGroup(self , head: ListNode, k: int) -> ListNode: # write code here if k==1&nbs***bsp;head is None: return head newHead = fast = slow = ListNode(-1) fast.next = head slow.next = head while True: for _ in range(k): fast = fast.next if fast is None: break if fast is None: break else: pre = None tail = cur = slow.next for _ in range(k): tmp = cur.next cur.next = pre pre = cur cur = tmp slow.next= pre tail.next = cur fast = slow = tail return newHead.next
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param head ListNode类 # @param k int整型 # @return ListNode类 class Solution: def reverseKGroup(self , head: ListNode, k: int) -> ListNode: # write code here a=[] s=[] while head:#遍历所有节点 a.append(head.val)#将遍历到的节点加入a列表 head=head.next if len(a)==k:#如果长度达到k则翻转 for i in range(k): s.append(a.pop()) if len(a)<k:#长度不足k，直接保留 for i in range(len(a)): s.append(a[i]) res=ListNode(0)#列表转链表 cur=res for i in s: cur.next=ListNode(i) cur=cur.next return res.next
## 递归实现 class Solution: def reverse(self, head, k): p = head if head is None: return p end = ListNode(head.val) start = end for i in range(1, k): if head is None: return p if head.next is None: return p head = head.next node = ListNode(head.val) node.next = start start = node end.next = self.reverse(head.next, k) return start def reverseKGroup(self , head: ListNode, k: int) -> ListNode: if head is None: return head start = self.reverse(head, k) return start
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param head ListNode类 # @param k int整型 # @return ListNode类 # class Solution: def reverseKGroup(self , head: ListNode, k: int) -> ListNode: # write code here new_head = ListNode(0) new_head.next=head c=0 last=new_head cur = new_head while cur: if c==k: cur=self.reverse(last,k) last=cur c=0 c+=1 cur=cur.next return new_head.next def reverse(self, last, k): queue_head=last.next for i in range(1, k): next=queue_head.next queue_head.next=next.next next.next=last.next last.next=next return queue_head
class Solution: def reverseKGroup(self , head: ListNode, k: int) -> ListNode: # write code here res=ListNode(0) res.next=head pre=res # 指向进行反转部分链表的前序 cur=head # 指向进行反转部分链表头 while cur: tail=cur for i in range(0,k): # 判断要不要翻转 if tail==None: return res.next else: tail=tail.next for i in range(1,k): # 翻转 temp=cur.next cur.next=temp.next temp.next=pre.next pre.next=temp cur=cur.next # 指向下一部分列表头 for i in range(0,k): pre=pre.next return res.next一次性循环跑完……
def reverseKGroup(self , head: ListNode, k: int) -> ListNode: # write code here newHead = ListNode(0) newHead.next = head i = 0 while head: head = head.next i += 1 total_num = i reverse_time = total_num // k head = newHead.next pre = newHead while reverse_time>0: reverse_time -= 1 for i in range(k-1): tmp = head.next head.next = tmp.next tmp.next = pre.next pre.next = tmp if reverse_time != 0: head = head.next for i in range(k): pre = pre.next return newHead.next
def reverseKGroup(self , head: ListNode, k: int) -> ListNode: # write code here le = 0 # 虚拟头结点 hv = ListNode(0) hv.next = head t = hv # 计算长度 while t.next is not None: le += 1 t = t.next rev_time = le // k # 共需翻转rev_time次 pre = hv cur = hv.next p,c = pre,cur # 暂存pre和cur for _ in range(rev_time):# 共需翻转rev_time次 for _ in range(k):# 每次翻转k个元素 temp = cur.next cur.next = pre pre = cur cur = temp # 连接头尾结点并更新p和c p.next = pre p = c c.next = cur c = cur return hv.next
class Solution: def reverseKGroup(self , head: ListNode, k: int) -> ListNode: # write code here tail = head for _ in range(k): if tail is None: return head tail = tail.next pre = None cur = head for _ in range(k): temp = cur.next cur.next = pre pre = cur cur = temp head.next = self.reverseKGroup(cur, k) return pre
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param head ListNode类 # @param k int整型 # @return ListNode类 # class Solution: def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode: # write code here p0 = ListNode(-1) p0.next = head p1 = head p3 = head p2 = p0 for _ in range(1, m): p1 = p1.next p2 = p2.next p3 = p3.next for _ in range(m, n+1): if not p3: return p0.next, True p3 = p3.next for _ in range(m, n): temp = p1.next p1.next = temp.next temp.next = p2.next p2.next = temp return p0.next, False def reverseKGroup(self , head: ListNode, k: int) -> ListNode: # write code here if not head&nbs***bsp;not head.next&nbs***bsp;k == 1: return head terminate = False start = 0 while not terminate: head, terminate = self.reverseBetween(head, start+1, start+k) start += k return head
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param head ListNode类 # @param k int整型 # @return ListNode类 #思路 #1.对原链表剩余部分每k个节点计数为一组，切断链表 #2.将切出的子链表翻转，记录翻转后链表头节点，尾结点 #3.将每次切出并翻转的链表拼接到结果链表 #4.重复1-3，直至原链表遍历结束 class Solution: #翻转链表方法 def reverseChain(self,head:ListNode): tail = None p = head while p: temp = p.next p.next = tail tail = p p = temp return tail #获取链表尾结点方法 def getTain(self,head:ListNode): p = head i = 1 while p.next: i += 1 p = p.next return p,i def reverseKGroup(self , head: ListNode, k: int) -> ListNode: # write code here #如果k为1，返回原链表 if k == 1: return head #如果k比原链表长度大，返回原链表 if head and self.getTain(head)[1] < k: return head p = head i = 1 s = None res = None while p: #获取每一段切分链表的头结点 if i%k == 1: s = p p = p.next i += 1 #切分完成后与结果链表res连接 elif i%k == 0: temp = p.next p.next = None #首次切分时 if i == k: res = self.reverseChain(s) else: res_tail = self.getTain(res)[0] res_tail.next = self.reverseChain(s) i += 1 p = temp else: p = p.next i += 1 #如果剩余不足k长度的子链表，直接连接入结果链表 if not p and (i-1)%k != 0: res_tail = self.getTain(res)[0] res_tail.next = s return res
class Solution: def reverseKGroup(self , head: ListNode, k: int) -> ListNode: # write code here if not head: return None res = ListNode(-1) res.next = head pre = res cur = pre.next length = 0 while head: length+=1 head = head.next if length < k: return res.next else: for a in range(1,length%k+1): #找到循环位置 for i in range(1,(a-1)*k+1): pre = cur cur = cur.next #开始循环 for i in range(1,k): temp = cur.next cur.next = temp.next temp.next = pre.next pre.next = temp return res.next
class Solution: def reverseKGroup(self , head: ListNode, k: int) -> ListNode: # write code here if k==1: return head if not head: return head linklist = [] cnt = 0 cur_k = [] while head: cur_k.append(head) cnt += 1 if cnt == k: linklist.extend(cur_k[::-1]) cur_k = [] cnt=0 head = head.next linklist.extend(cur_k) dummy_head = ListNode(-1) last_node = dummy_head for node in linklist: last_node.next = node last_node = node last_node.next = None return dummy_head.next
class Solution: def reverseKGroup(self , head: ListNode, k: int) -> ListNode: # write code here dummy = ListNode(0) dummy.next = head j = 0 # 获取链表长度 while head: head = head.next j = j + 1 if j == 0: return total_times = j // k # 需要翻转的总次数 times = 0 # 第times次翻转 i = 0 previous = dummy head = dummy.next while previous.next and times < total_times: # 进入第times次翻转 # 要反转k个元素的链表只需操作k-1次，故先令i+1 i = i + 1 while i // k == times: previous_next = previous.next previous.next = head.next head.next = previous.next.next previous.next.next = previous_next i = i + 1 previous = head head = head.next times = times + 1 return dummy.next
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
