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.
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
func reverseKGroup(head *ListNode, k int) *ListNode {
if head==nil{
return nil
}
if head.Next==nil{
return head
}
p:=head
var ret*ListNode
var dun *ListNode=head
var tail *ListNode
for p!=nil{
count:=0
for ;count<k;count++{
if p!=nil{
p=p.Next
}else {
break
}
}
if count==k{
tmp:=revert1(dun,p)
if ret==nil{
ret=tmp
}
if tail==nil{
tail=dun
}else {
tail.Next=tmp
tail=dun
}
dun=p
}else {
if ret==nil{
ret=head
return ret
}else {
tail.Next=dun
}
}
}
return ret
}
func revert1(head*ListNode,tail*ListNode)*ListNode {
if head==nil{
return nil
}
p:=head.Next
pre:=head
for p!=tail{
tmp:=p.Next
p.Next=head
head=p
pre.Next=tmp
p=tmp
}
return head
}
递归不满足内存约束
func reverseKGroup(head *ListNode, k int) *ListNode {
if head==nil{
return nil
}
if head.Next==nil{
return head
}
var ret*ListNode
var p *ListNode=head
i:=1
var bef *ListNode
for ;i<k;i++{
if p!=nil{
bef=p
p=p.Next
}else{
break
}
}
if i<k{
return head
}
if i==k{
if p.Next==nil{
return head
}
if p==nil{
var rethead*ListNode
var rettail*ListNode
rethead,rettail=revert(head)
rettail.Next=nil
ret= rethead
}else {
tmpret:=reverseKGroup(p,k)
var rethead*ListNode
var rettail*ListNode
bef.Next=nil
rethead,rettail=revert(head)
rettail.Next=tmpret
ret= rethead
//retvert
}
}else {
return head
}
return ret
}
func revert(head*ListNode) (*ListNode,*ListNode){
var rethead *ListNode
var rettail *ListNode
if head==nil{
return nil,nil
}
if head.Next==nil{
return head,head
}
tmphead,tmptail:=revert(head.Next)
tmptail.Next=head
rettail=head
rethead=tmphead
return rethead,rettail
}