C++ 没有用递归和栈的解题思路

首先需要明确几个设计点

1. 链表为空和链表只有一个节点情况: 直接 return head.

if(head==NULL || head->next==NULL){
          return head;
      }

2. 如果节点数量大于等于2,需要虚拟哨兵节点指向头节点,去头节点特殊化,并创建一个pre指针,指向每一个k组的头.

ListNode* guard = new ListNode(0);//整个链表的哨兵节点
guard->next = head; // 指向head节点
ListNode* pre = guard; //每一个组的哨兵节点

3. 创建一个end指针(有些解说大佬会说这是fast指针)比cur指针多遍历K个节点.

初始化如下:

ListNode* cur = head;  //每一组的唯一钉子节点
ListNode* end = head; 

此时分为两种情况继续讨论:

1. 链表元素个数<k, 此时end指针与cur指针指向的节点之间相差不足k个. 此时将end指针赋值为NULL, 程序的结果是直接返回原链表顺序,即** return head**.
2. 链表元素个数>=k, 此时end指针与cur指针指向的节点之间保持相差等于k个.启动for循环, cur也开始遍历链表,并与end之间只保持k个元素距离. 初始化移动 end指针代码如下:

int i=0; //因为i接下来也要用,所以初始化没有放在循环体内
for(;i<k;i++){
     if(end->next!=NULL){ //必须判断下是否为空,不然会报堆栈溢出错误
          end = end->next;     
    }
    else{
      end = NULL;
      i++;
      break;
       }
 }
 int n=i; //为接下来i = k-(n%k)做铺垫

举个例子:

4.在3的第二种情况的基础下(end!=NULL),判断循环体的i整除k是否有余数, 如果有余数, 则反转链表元素.如果没有元素, 则进入下一个k组的链表反转.

	 for(i=1;end!=NULL;i++){
          if(i%k!=0){
              ListNode* temp = cur->next; // temp指针指向钉子节点的下一个节点
              cur->next = temp->next;  //将cur->next->next赋值给cur->next
              temp->next=pre->next;   //将每一个k组的哨兵pre指向的下一节点地址赋值给temp->next
              pre->next=temp; 
          }else {
            pre=cur; //当i%k为0时,代表当前k组最后一个元素已经反转完毕,将哨兵指针pre移到cur当前位置, 并将cur移到下一个节点位置.
            cur=cur->next;
          }
           end = end->next; //end指针也向后移动一位,与cur保持等距离k
           ++n; //当前链表节点数量++
      }

5.在4的基础上,end指针指向为空,链表遍历完毕.此时cur和end之间只相差k个元素, 因此需要确定最后一组的结束位置.(最后也是最脑筋急转弯的地方)

分情况讨论:

1. 假定cur指针指向的节点称为最后一组, end指针指向的节点称为剩余节点组. cur指向的是每一组除最后一位的任意节点(意味着剩余节点不足k个),则反转所有节点后,end所在的剩余节点组无需反转,直接输出最后链表.
2. cur指针指向的正好是最后一组的第k个节点,则剩余节点正好等于k,则剩余节点组均反转,输出结果. 代码如下:

  i=k-(n%k); //判断最后一组还有几个元素需要反转
  while(i-->1){
     ListNode* temp = cur->next;
        cur->next = temp->next;
        temp->next=pre->next;
        pre->next=temp;  
       } 
return guard->next;