1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| # Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head, tail):
if not head:
return head
# 注意这里需要保留与tail之后数据的连接
pre = tail.next
p = head
while pre != tail:
q = p.next
p.next = pre
pre = p
p = q
return pre, head
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
dummy = ListNode()
dummy.next = head
left = dummy
tail = dummy
# print('left,right,head',left.val, right.val,head.val)
while head:
for i in range(k):
tail = tail.next
if not tail:
return dummy.next
# print('head,tail',head,tail)
# 开始翻转前先记录被翻转部分的左右两部分
right = tail.next
new_head, new_tail = self.reverseList(head, tail)
# print('new_head,new_tail',new_head,new_tail)
# 翻转后的新链表连接到原链表中间
left.next = new_head
new_tail.next = right
# 重新初始化待翻转链表的head、tail以及左半部分
head = new_tail.next
tail = new_tail
left = new_tail
return dummy.next
|
