25. K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

递归法：

两个前提

  1. 先了解 206. 反转链表，这题

  2. 双指针思想，尾指针滑动，确定链表k区间

    1. //递归，通法，面试专用
    2. func reverseKGroup(head *ListNode, k int) *ListNode {
    3.  cur := head                            //1，实际指针cur，前进指针pre
    4.  for i := 0; i< k ;i++ {
    5.      if cur == nil{                     //判断【】空链表
    6.          return head                    //一：分组，不足k个的，还是原来head前进。不足改这里    
    7.      }
    8.      cur = cur.Next    //满足k个的，记录为cur，准备翻转； 这里得到的最后一个cur，是下一个k group的头指针;
    9.  }
    11.  //二：递归返回的新tail，作为pre虚拟节点？，和新链表连接
    12.  pre := reverseKGroup(cur, k)            //注意：pre= var *ListNode；新的head=cur
    13.  modn := head                            //2，返回前进指针pre就行，modn实际指针
    15.  for i :=0; i < k; i++ {
    16.      temp := modn.Next   //三：翻转四件套，head=cur
    17.      modn.Next = pre
    18.      pre = modn
    19.      modn = temp
    20.  }
    21.  return pre  //以k为单位，层层前进
    22. }

    迭代法：解题思路

    思路上很简单，就是每遍历k个元素做一次链表反转
    coding时有很多要注意的：

  • prev: 保存已经处理好的链表的末尾
  • head: 正在处理的链表头
  • tail: 正在处理的链表部分的尾部
  • ph: 反转后的局部链表头部==上一个tail
  • pt: 反转后的局部链表尾部，尾部的Next指向下一个head.2 == 上一个head.1
//迭代法，超级考验代码能力；
//背吧：写不出来的，三步走
func reverseKGroup(head *ListNode, k int) *ListNode {
    dummy := &ListNode{Next: head}          //定义新链表的固定语句
    prem := dummy                           //pre: 保存已经处理好的链表的末尾

    for head != nil {                        //一：分组
        cur := prem                         //万恶之源：为啥不直接=head ？不管他，逻辑就通了：cur就是headの化身

        for i := 0; i < k; i++ {            //截取k个一段
            cur = cur.Next                  //前进指针
            if cur == nil {                 //不能去掉cur判定, 8=3+3+2
                return dummy.Next   
            }
        } 
                                            //二：翻转
        tmp := cur.Next                     // tmp = head（变动中）；tmp前进指针              
        head, cur = myReverse(head, cur)    // head=m;   cur=n ->下一组的prem

        //三：合并
        prem.Next = head                    //前序指针：真头；  直接连接边角料，不用指针;        怎么背？三个概念依次出现！head在前
        cur.Next = tmp                      //后序指针：真尾；  2.1：合并首尾，边角料，此时 m=head, n=cur;

        prem = cur                          //虚头：当前；   前进指针，        head首尾呼应！ 怎么背？prem和head两个真实的，不用cur虚拟！=虚拟cur
        head = cur.Next                     //真头：当前下；  2.2：前进k内的顺序 后k的头 == 中k的尾，前进指针
    }
    return dummy.Next       
}


func myReverse(head, cur *ListNode) (*ListNode, *ListNode) {
    pre := cur.Next                         //先头指针；其实不能理解为prem的下一个；只能理解为head的下一个
    modn := head                            //modn = cur（现实中）

    for pre != cur {                        // cur = nil    m,n中的n
        temp := modn.Next                   //翻转四件套，两个k合并，所以一起翻转两个
        modn.Next = pre
        pre = modn
        modn = temp
    }
    return cur, head
}