题目：
给出一个链表，每k个一组进行翻转，并返回翻转后的链表。
如果节点总数不是k的整数倍，那么将剩余节点保持原序返回。
例子：
给出：1->2->3->4->5, k=3
输出：3->2->1->4->5
说明：
1. 你的算法只能使用常数的额外空间
2. 不能单纯的改变节点的值，需要对实际节点进行交换
首先要判断链表长度是否大于k，然后再进行分组翻转。由于会有剩余部分，不要忽略翻转完毕后对剩余部分的重新连接。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#python 3
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseKGroup(self, head, k):
length = 0
start = head
pre = cur = new = None
while head:
head = head.next
length += 1
if k > length: return start #!!!start is the original head, head already move to NULL!!!
t = length // k
while t > 0:
cur, new = self.reverse(start, k)
if pre is None:
res = cur #!!!cur is the new head not start!!!
else:
pre.next = cur
pre = start
start = new
t -= 1
pre.next = start #!!!do not forget to connect the rest of the list!!!
return res
def reverse(self, start, k):
cur, pre = start, None
while k > 0:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
k -= 1
return pre, cur
