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。
此算法使用O（k）额外空间。

//用于在给定大小的组中反转链接列表的C ++程序
// #include 
using namespace std;
 
// Link list node
struct Node
{
    int data;
    struct Node* next;
};
 
/* Reverses the linked list in groups
   of size k and returns the pointer
   to the new head node. */
struct Node* Reverse(struct Node* head,
                     int k)
{
    //创建一个Node*堆栈
    stack mystack;
    struct Node* current = head;
    struct Node* prev = NULL;
 
    while (current != NULL)
    {
        //终止循环无论是当前== NULL还是计数> = k
        int count = 0;
        while (current != NULL &&
               count < k)
        {
            mystack.push(current);
            current = current->next;
            count++;
        }
 
        //依次弹出堆栈的元素
        while (mystack.size() > 0)
        {
            //如果尚未开始最终列表。
            if (prev == NULL)
            {
                prev = mystack.top();
                head = prev;
                mystack.pop();
            }
            else
            {
                prev->next = mystack.top();
                prev = prev->next;
                mystack.pop();
            }
        }
    }
 
    //最后一个元素的下一个将指向NULL。
    prev->next = NULL;
 
    return head;
}
 
//实用功能
//用于推送节点的功能
void push(struct Node** head_ref,
          int new_data)
{
    //分配节点
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
 
    //放入数据
    new_node->data = new_data;
 
    //链接新节点的旧列表
    new_node->next = (*head_ref);
 
    //将头移动以指向新节点
    (*head_ref) = new_node;
}
 
//用于打印链接列表的功能
void printList(struct Node* node)
{
    while (node != NULL)
    {
        printf("%d ", node->data);
        node = node->next;
    }
}
 
//驱动程序代码
int main(void)
{
    //从空列表开始
    struct 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);
 
    printf("给定的链接列表");
    printList(head);
    head = Reverse(head, 3);
 
    printf("反转的链接列表");
    printList(head);
 
    return 0;
}  

输出：

给定的链表
1 2 3 4 5 6 7 8 9 
翻转后的链表
3 2 1 6 5 4 9 8 7

时间复杂度 ：O(n*k)，其中n是给定链表的大小

辅助空间： O(1)