//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    
    length:=0
    pre:=head
    //计算链表长度
    for pre!=nil{
        length++
        pre = pre.Next
    }
    
    //k个一组的次数
    time:=length/k
    dummy:=new(ListNode)
    dummy.Next = head
    pre = dummy    //每一组前面的数,头插法,每次都把move放在pre后面
    var nexthead,move *ListNode
    for i:=0;i<time;i++{
        nexthead = pre.Next    //每个k长度的开头,逐渐变为末尾
        move = nexthead.Next//第二个,不断向后移动,把move插入到pre后面,
        for j:=0;j<k-1;j++{
            nexthead.Next = move.Next
            move.Next = pre.Next
            pre.Next = move
            move = nexthead.Next
        }
        //经过头插法,nexthead逐渐变为结尾,结束一轮循环时,nexthead变为结尾,是下一个k长度的pre,
        pre = nexthead  //下一个k同样的方式,头插法放pre后面
        
    }
    return dummy.Next
}

迭代法,还有递归法,

 

2.反转从m到n位置的链表 

还是头插法,找到m前面一个节点,后面的都放在pre之后,

func reverseBetween(head *ListNode, m int, n int) *ListNode {
    if head==nil{
        return head
    }

    dummy:=new(ListNode)
    dummy.Next = head
    pre:=dummy
    //先找到m前面的节点
    for i:=0;i<m-1;i++{
        pre = pre.Next
    }

    var nexthead,move *ListNode
    nexthead = pre.Next
    move = nexthead.Next

    //头插法,反转n-m次
    for j:=0;j<n-m;j++{
        nexthead.Next = move.Next
        move.Next = pre.Next
        pre.Next = move
        move = nexthead.Next
    }
    return dummy.Next
}