Description:
Given a linked list, reverse the nodes of a linked list _k_ at a time and return its modified list. _k_ is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of _k_ then left-out nodes in the end should remain as it is. You may not alter the values in the nodes, only nodes itself may be changed. Only constant memory is allowed.
For example, Given this linked list: 1->2->3->4->5
For _k_ = 2, you should return: 2->1->4->3->5
For _k_ = 3, you should return: 3->2->1->4->5
解法：
一般在处理链表问题时，我们大多时候都会在开头再加一个dummy node，因为翻转链表时头结点可能会变化，为了记录当前最新的头结点的位置而引入的dummy node。具体到思路，每次以k为分段，翻转这k个节点，整体需要翻转的数减去k，如果剩余翻转点小于k无需继续进行翻转。翻转的过程中从前往后扫描，需要pre,last,tmp和cur四个指针。具体代码如下：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# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if(head == None or k == 1):
return head;
dummy = ListNode(-1);
dummy.next = head;
pre = dummy;
cur = head;
num = 0;
while(cur):
cur = cur.next;
num+=1;
while(num>=k):
cur = pre.next;
last = cur;
for i in range(k):
last = last.next;
for i in range(k):
t = cur.next;
cur.next = last;
last = cur;
cur = t;
tmp = pre.next;
pre.next = last;
pre = tmp;
num -= k;
return dummy.next;