@author: ZZQ
@software: PyCharm
@file: ReverseList.py
@time: 2018/11/6 15:13
题目要求：给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。
示例 :
给定这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
说明 :
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
思路：针对每个子链表进行反转，需要在每次做翻转时记录当前子链表的首节点，尾节点以及下一个待翻转链表的首节点。
需要注意当剩余节点数小于k的情况以及链表本身为空的情况。
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution():
def __init__(self):
pass
def reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if k == 0 or k == 1 or head is None or head.next is None:
return head
NextListHeadNode = head
NewH = ListNode(0)
tempNewH = ListNode(0)
time = 0
while head.next is not None and tempNewH is not None:
if time == 0:
count, PreListFirstNode, PreListLastNode, NextListHeadNode = self.ReverseKList(head, k)
time += 1
NewH = PreListFirstNode
PreListLastNode.next = NextListHeadNode
tempNewH = NewH
if count < k:
for i in range(count):
tempNewH = tempNewH.next
else:
for i in range(count - 1):
tempNewH = tempNewH.next
else:
head = NextListHeadNode
count, PreListFirstNode, PreListLastNode, NextListHeadNode = self.ReverseKList(head, k)
PreListLastNode.next = NextListHeadNode
tempNewH.next = PreListFirstNode
time += 1
tempNewH = tempNewH
if count < k:
for i in range(count+1):
tempNewH = tempNewH.next
else:
for i in range(count):
tempNewH = tempNewH.next
return NewH
def ReverseKList(self, head, k):
PreH = ListNode(0)
PostH = head.next
count = 0
while head is not None and count < k:
head.next = PreH
PreH = head
head = PostH
if PostH is not None:
PostH = PostH.next
count += 1
if head is None and count < k: # 如果剩余的节点个数小于k，则返回原来的节点顺序
lastFirstNode = self.ReverselastList(PreH)
lastEndnode = lastFirstNode
for i in range(count-1):
lastEndnode = lastEndnode.next
lastEndnode.next = None
return count, lastFirstNode, lastEndnode, None
else:
tempPreH = PreH
tt = count
while tt-1 > 0:
tempPreH = tempPreH.next
tt -= 1
return count, PreH, tempPreH, head
# 返回当前子链表经过翻转后的首节点，尾节点以及下一个子链表未反转前的首节点
def ReverselastList(self, head):
PreH = ListNode(0)
PostH = head.next
while head is not None:
head.next = PreH
PreH = head
head = PostH
if PostH is not None:
PostH = PostH.next
return PreH.next