25.?k個一組翻轉鏈表
給出一個鏈表,每k?個節(jié)點一組進行翻轉弯屈,并返回翻轉后的鏈表。
k?是一個正整數(shù)缴淋,它的值小于或等于鏈表的長度。如果節(jié)點總數(shù)不是k?的整數(shù)倍泄朴,那么將最后剩余節(jié)點保持原有順序重抖。
示例 :
給定這個鏈表:1->2->3->4->5
當k?= 2 時,應當返回:?2->1->4->3->5
當k?= 3 時祖灰,應當返回:?3->2->1->4->5
說明 :
你的算法只能使用常數(shù)的額外空間钟沛。
你不能只是單純的改變節(jié)點內部的值,而是需要實際的進行節(jié)點交換局扶。
# 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
? ? ? ? newTail = None
? ? ? ? begin = None
? ? ? ? isFirst = True
? ? ? ? isOver = False
? ? ? ? isEnd = False
? ? ? ? while not isOver and head.next!=None:
? ? ? ? ? ? lenght = k
? ? ? ? ? ? headI = head
? ? ? ? ? ? headJ = headI
? ? ? ? ? ? while lenght>1 and headI.next!=None :
? ? ? ? ? ? ? ? headI = headI.next
? ? ? ? ? ? ? ? lenght-=1
? ? ? ? ? ? if lenght>1 or headI.next==None :
? ? ? ? ? ? ? ? isOver = True
? ? ? ? ? ? if lenght>1:
? ? ? ? ? ? ? ? isEnd = True
? ? ? ? ? ? head = headI.next
? ? ? ? ? ? headI.next=None
? ? ? ? ? ? if not isEnd:
? ? ? ? ? ? ? ? data = self.fanzhuan(headJ)
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? self.newHead = headJ
? ? ? ? ? ? ? ? data = headI
? ? ? ? ? ? if isFirst:
? ? ? ? ? ? ? ? newTail = data
? ? ? ? ? ? ? ? begin = self.newHead
? ? ? ? ? ? ? ? isFirst = False
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? newTail.next = self.newHead
? ? ? ? ? ? ? ? newTail = data
? ? ? ? if not isOver and head.val!=None:
? ? ? ? ? ? newTail.next = head
? ? ? ? return begin
? ? newHead = None
? ? def fanzhuan(self, head):
? ? ? ? if head.next==None:
? ? ? ? ? ? self.newHead = head
? ? ? ? ? ? return head
? ? ? ? else:
? ? ? ? ? ? data = self.fanzhuan(head.next)
? ? ? ? ? ? head.next = None
? ? ? ? ? ? data.next = head
? ? ? ? ? ? return head