Given a linked list, reverse the nodes of a linked list k at a time and return its modified 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
注意：
1.空指针和只有一个节点之类的边界情况。
- 更新链表之后，没有将链表尾部置空，造成它指向其他的节点，构成环，或者想拆下链表的一部分时没有把那部分的尾部置空，构成环。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
```
class Solution(object):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
def reverse(self,head):
newHead = head
head = head.next
while head != None:
t = head
head = head.next
t.next = newHead
newHead = t
return newHead
def reverseKGroup(self, head, k):
if head == None or head.next == None:
return head
indexNode = head.next
newHead = head
newTailer = head
newTailer.next = None
for i in range(k-1):
if indexNode == None:
self.reverse(newHead)
t = newHead
newHead = newTailer
newTailer = t
break
t = indexNode
indexNode = indexNode.next
t.next = newHead
newHead = t
head = newHead
listEndNode = newTailer
while indexNode != None:
# get the first one
newHead = indexNode
newTailer = indexNode
indexNode = indexNode.next
newTailer.next = None
# get the k-1 node
for i in range(k-1):
if indexNode == None:
self.reverse(newHead)
t = newHead
newHead = newTailer
newTailer = t
break
t = indexNode
indexNode = indexNode.next
t.next = newHead
newHead = t
listEndNode.next = newHead
#reset the end value
listEndNode = newTailer
# important next must set null , or the next may pointor othor palce
listEndNode.next = None
return head
看我改进版，减少初始判断。。。
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
def reverse(self,head):
newHead = head
head = head.next
while head != None:
t = head
head = head.next
t.next = newHead
newHead = t
return newHead
def reverseKGroup(self, head, k):
if head == None or head.next == None:
return head
indexNode = head
head = ListNode(0)
listEndNode = head
while indexNode != None:
# get the first one
newHead = indexNode
newTailer = indexNode
indexNode = indexNode.next
newTailer.next = None
# get the k-1 node
for i in range(k-1):
if indexNode == None:
self.reverse(newHead)
t = newHead
newHead = newTailer
newTailer = t
break
t = indexNode
indexNode = indexNode.next
t.next = newHead
newHead = t
listEndNode.next = newHead
#reset the end value
listEndNode = newTailer
# important next must set null , or the next may pointor othor palce
listEndNode.next = None
return head.next
