题解 | #链表中的节点每k个一组翻转#
链表中的节点每k个一组翻转
http://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e
思路如下: 通过链表总长度来确定翻转次数,并循环依次翻转。翻转的范围控制为k即可。
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
#1. 空链表直接return
if not head: return
#2. 计算链表的总长度 len_list
numHead = head
numList = []
while numHead:
numList.append(numHead.val)
numHead = numHead.next
len_list = len(numList)
#3. 通过总长度来确定翻转次数,并循环依次翻转
#设置m和n是翻转的范围起点和终点,在这里,我们的范围为k
m = 1
n = k
for _ in range(int(len_list/k)):
head = self.reverseK(head, m, n)
#进行下一组范围为k的链表翻转
m += k
n += k
return head
#4.翻转链表(m,n)部分。不做解释。
def reverseK(self, head, m, n):
N = ListNode(-1)
N.next = head
pre = N
for _ in range(m-1):
pre = pre.next
cur = pre.next
for _ in range(n-m):
temp = cur.next
cur.next = temp.next
temp.next = pre.next
pre.next = temp
return N.next