K个一组翻转链表(反转一个链表)

1、主问题：K个一组翻转链表

• 问题描述 ：给定一个链表，每K个节点一组进行翻转，最后返回翻转后的链表；
• 问题细节 ：K是一个正整数，它的值小于或等于链表的长度；如果节点总数不是k的整数倍，那么就将最后的节点保持原有的顺序；

• 示例 ： 给你这个链表：1->2->3->4->5

        当 k = 2 时，应当返回: 2->1->4->3->5<br />                   当 k = 3 时，应当返回: 3->2->1->4->5

• 说明 ： 1. 算法只能使用常数的额外空间； 2. 不能只是单纯的改变节点内部的值，需要实际进行节点转换；

2、问题分析

本问题包含一个子问题： 链表的翻转；假设链表的长度为L, 那么这里需要翻转的子链表的次数为L/K次；除此之外，还需要将每个翻转后的子链表头节点和尾节点链接起来成为一个新的链表；

3、子问题：链表翻转

• 分析：链表翻转就是一个不断将 原先前面节点指向后面节点 变成 后面节点指向前面节点 的过程。
• 解题思路：链表翻转可以采用迭代方法和递归两种方法；

1、迭代：遍历所有的节点，逐个改变前一个节点与后一个节点的指向；

• 迭代代码：

  /**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
  ListNode* reverseList(ListNode* head)
  {
    // 空链表 || 只有一个节点
    if (head == NULL || head->next == NULL)
        return head;
    ListNode* pre_node = NULL;      // 指向当前处理的节点的前一个节点
    ListNode* curr_node = head;     // 指向当前处理的节点
    ListNode* next_node = curr_node->next;  // 指向当前处理节点的后一个节点
    head->next = pre_node /* NULL */;
    while(next_node != NULL)        // next_node为空，表明翻转完成，此时curr_node指向最后一个节点
    {
        ListNode* temp_node = next_node->next;  // 暂存next_node的下一个节点
        next_node->next = curr_node;            // 将后一个节点的指向前一个节点
  
        // 更新curr_node与next_node，便于下一次迭代
        curr_node = next_node;
        next_node = temp_node;
    }
    return curr_node;
  }
  

  2、递归：从第i个节点以后的链表翻转与从第i+1个节点以后的链表的翻转是同样的操作，所以这里有递归的影子； 递归过程中要注意链表的节点前后之间如何链接起来的问题 。

• 递归代码：

  ListNode* reverseList(ListNode* head)
  {
    // 递归结束：基础问题
    if (head == NULL || head->next == NULL)
        return head;
    ListNode* reversed_head = reverseList(head->next); // 翻转head后面的子链表，最终返回的就是最后一个节点
  
    // 递归回溯：head->next指向最后一个节点，那么需要head->next反指向其前面的节点
    head->next->next = head;
    // 此时head指向head->next，所以需要断开head指向head->next；
    // 而且在末尾head需要指向NULL标志链表结尾 
    head->next = NULL; 
  
    return reversed_head;
  }
  

  4、回到主问题： K个一组翻转链表

• 分析：针对head为头节点的链表，每K个结点一组进行翻转，最后链接每个翻转后的子链表；

• 解题思路：

1、迭代：获取每K个节点的头结点head与尾结点tail，对[head, tail]之间的K个结点进行翻转(单链表翻转)， 返回翻转以后的头结点reverse_head和尾结点reverse_tail, 并链接前后子链表；

图片引用链接，侵权提醒删除

• 迭代代码 ```cpp ListNode reverseList(ListNode head) { if (head == NULL || head->next == NULL)

    return head;
  

  ListNode curr = head; ListNode next = curr->next; while(next != NULL) {

    ListNode* temp = next->next;
    next->next = curr;
    curr = next;
    next = temp;
  

  } return curr; }

ListNode reverseKGroup(ListNode head, int k) { ListNode* dummy = new ListNode(0); dummy->next = head;

ListNode* pre = dummy;
ListNode* curr = dummy;

while(curr.next != NULL)
{
    int cnt = 0;
    while(cnt < k && curr != NULL)
    {
        curr = curr->next;
        ++cnt;
    }
    // 表明已到达链表末尾
    if(curr == NULL)
        break;
    ListNode* start = pre->next;     // 待翻转子链表头结点
    ListNode* next = curr->next;     // 下一个子链表头结点
    curr->next = NULL;               // 断开前K节点的个子链表与后面的链接；便于reverseList翻转

    pre->next = reverseList(start);  // 翻转以后的子链表头指针

    // 翻转以后的子链表的尾指针与后面未翻转的链表
    start->next = next;
    // 更新pre与curr的指向用于下一次的翻转
    pre = start;
    curr = pre;
}
return dummy->next;

}

2、递归：获取每K个节点的头结点head与尾结点tail，对[head, tail]之间的K个结点进行翻转(单链表翻转)，再将翻转后的子链表与后面的链表链接起来；第二个K个结点的翻转-链接操作与第一次完全相同，故可采用递归来做；
```cpp
ListNode* reverseList(ListNode* head, ListNode* tail)
{
    if (head == tail)
        return head;
    ListNode* curr = head;
    ListNode* next = curr->next;
    while(next != tail)
    {
        ListNode* temp = next->next;
        next->next = curr;
        curr = next;
        next = temp;
    }
    return curr;
}

ListNode* reverseKGroup(ListNode* head, int k)
{
    ListNode* sub_tail = head;
    int cnt = 0;
    while(sub_tail != NULL && cnt < k)
    {
        sub_tail = sub_tail->next;
        cnt++;
    }
    // 基本情况：子链表节点数小于k个，不翻转直接返回子链表头结点
    if(cnt < k)
        return head;
    ListNode* curr = NULL;    // curr = NULL的赋值很重要，
    ListNode* sub_head = head;
    // curr指向翻转以后子链表的头结点
    curr = reverseList(sub_head, sub_tail);  // sub_tail指向子链表末尾的后一个节点
    // head为之链表的头结点，链表翻转以后，其应该指向后面未翻转的链表的头结点：reverseKGroup(sub_tail, k)返回的结果
    head->next = reverseKGroup(sub_tail, k);
    return curr;
}