C++程序 分组反转链表 – 1

给定一个链表，编写一个函数来反转每k个节点的链表（其中k是函数的输入）。

例子：

输入 : 1->2->3->4->5->6->7->8->NULL，K = 3

输出 : 3->2->1->6->5->4->8->7->NULL

输入 : 1->2->3->4->5->6->7->8->NULL，K = 5

输出 : 5->4->3->2->1->8->7->6->NULL

算法： 反转 (head, k)

• 反转第一个大小为k的子列表。反转时跟踪下一个节点和上一个节点。将指向下一个节点的指针设为 next ，将指向上一个节点的指针设为 prev 。请参见这篇文章中的反转链表
• head- >next = reverse(next, k) ( 对线路的其余部分进行递归调用，并将两个子列表链接在一起 )
• 返回 prev ( prev 成为列表的新头（请参见这篇文章的迭代方法的图解）

下面的图像显示了反转函数的工作原理：

下面是上述方法的实现：

// C ++程序反转链表
//按给定大小分组
#include <bits/stdc++.h>
using namespace std;
 
//链接列表节点
class Node
{
    public:
    int data;
    Node* next;
};
 
/* 反转链表在组中
  大小为k，并返回指针
  到新的头节点。 */
Node* reverse(Node* head, int k)
{
    // 基本情况
    if (!head)
        return NULL;
    Node* current = head;
    Node* next = NULL;
    Node* prev = NULL;
    int count = 0;
 
    // 反转链表的前k个节点
    while (current != NULL && count < k) 
    {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
        count++;
    }
 
    /* next现在是指向第（k+1）个节点的指针
    从当前开始递归调用列表。并使列表的其余部分
       作为第一个节点的下一个 */
    if (next != NULL)
        head->next = reverse(next, k);
 
    // prev是输入列表的新头
    return prev;
}
 
//实用函数
//将节点推入函数
void push(Node** head_ref,
          int new_data)
{
    // 分配节点
    Node* new_node = new Node();
 
    // 放入数据
    new_node->data = new_data;

    // 链接新节点的旧列表
    new_node->next = (*head_ref);
 
    // 将头指针移动到新节点
    (*head_ref) = new_node;
}
 
// 打印链接列表的函数
void printList(Node* node)
{
    while (node != NULL)
    {
        cout << node->data << " ";
        node = node->next;
    }
}
 
// 主函数
int main()
{
    // 从空列表开始
    Node* head = NULL;
 
    /* 创建连接列表
       1->2->3->4->5->6->7->8->9 */
    push(&head;, 9);
    push(&head;, 8);
    push(&head;, 7);
    push(&head;, 6);
    push(&head;, 5);
    push(&head;, 4);
    push(&head;, 3);
    push(&head;, 2);
    push(&head;, 1);
 
    cout << "给定链接列表 ";
    printList(head);
    head = reverse(head, 3);
 
    cout << "反转链表 ";
    printList(head);
 
    return (0);
}
//这些代码由rathbhupendra贡献```  

输出：

给定链接列表
1 2 3 4 5 6 7 8 9 
反转列表
3 2 1 6 5 4 9 8 7 

复杂度分析：

• 时间复杂度： O(n)。 只需要对列表进行一次遍历，且列表有n个元素。
• 空间复杂度： O(n/k)。 每个大小为n的链表，在递归过程中需要进行n/k或（n/k）+1次调用。