分类：LinkedList
考察知识点：LinkedList 递归 Reverse
最优解时间复杂度：**O(n) **
25. Reverse Nodes in k-Group
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.
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
Note:
- Only constant extra memory is allowed.
- You may not alter the values in the list's nodes, only nodes itself may be changed.
代码：
我的方法(超时了):
# 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
"""
node_list=[]
dummy=ListNode(0)
p=head
end=head
p1=dummy
count=0
while(p!=None):
node_list.append(p)
p=p.next
count+=1
if(count==k):
while(len(node_list)!=0):
p1.next=node_list.pop()
end=end.next
p1=p1.next
count=0
while(end!=None):
p1.next=end
end=end.next
p1=p1.next
return dummy.next
最佳方法:
# 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 head.next==None:
return head
#走一走
count=0
cur=head
while(cur!=None and count!=k):
cur=cur.next
count+=1
#reverse
if count==k:
cur=self.reverseKGroup(cur, k)
while(count):
count-=1
temp=head.next
head.next=cur
cur=head
head=temp
head=cur
return head
讨论：
1.大佬的方法超级快，基本上也是看懂了，但是感觉自己在reverse上还是十分的笨拙- -可能对reverse的题型这种还是要多加练习
2.这道题目可能不咋会考，emm所以似乎也无所谓了，但是还是要掌握reverse！
大佬方法,跪拜大佬
