• 分類：LinkedList

• 考察知識點(diǎn)：LinkedList 遞歸 Reverse

• 最優(yōu)解時間復(fù)雜度：**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的題型這種還是要多加練習(xí)
2.這道題目可能不咋會考，emm所以似乎也無所謂了，但是還是要掌握reverse！

大佬方法,跪拜大佬