C++程序 将给定链表的最后元素移动到前面

编写一个函数，在给定的单链表中将最后一个元素移动到前面。例如，如果给定的链表是1->2-> 3-> 4-> 5，则该函数应将列表更改为5-> 1-> 2-> 3-> 4。

算法： 遍历链表直到最后一个节点。使用两个指针：一个用于存储最后一个节点的地址，另一个用于存储倒数第二个节点的地址。循环结束后执行以下操作。

1. 使倒数第二个节点成为最后一个节点（secLast->next = NULL）。
2. 将最后一个节点设置为头部（last->next = * head_ref）。
3. 将最后一个节点设置为头部（* head_ref = last）。

/* C ++程序将最后一个元素移动
   到给定链接的前面*/
#include <bits/stdc++.h>
using namespace std;
 
//链接列表节点
class Node
{
    public:
    int data;
    Node *next;
};
 
/*此处我们使用双指针
   head_ref，因为我们改变了
   此功能内的链接列表的头*/
void moveToFront（Node **head_ref）
{
    /*如果链接列表为空，或者
       它仅包含一个节点，
       则不需要执行任何操作，
       直接返回*/
    if (* head_ref == NULL ||
       （* head_ref）-> next == NULL）
        返回;
 
    /*初始化其次
       和最后一个指针*/
    Node *secLast = NULL;
    Node *last = * head_ref;
 
    /*循环结束后，secLast包含以下内容
       链接列表中的倒数第二个节点的地址为
       last包含最后一个节点的地址
       在链接列表中*/
    while (last-> next！= NULL)
    {
        secLast = last;
        last = last-> next;
    }
 
    //将其次的下一个设置为NULL
    secLast-> next = NULL;
 
    //将最后一个节点的下一个设置为头节点
    last-> next = * head_ref;
 
    /*将头指针更改
       现在指向最后一个节点*/
    * head_ref = last;
}
 
//实用函数
/*函数添加一个节点
   在始发旅行中*/
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;
    }
}
 
// Driver code
int main ()
{
    Node * start = NULL;
 
    /*建造的链接列表是：
      1-> 2-> 3-> 4-> 5*/
    push（＆start，5）;
    push（＆start，4）;
    push（＆start，3）;
    push（＆start，2）;
    push（＆start，1）;
 
    cout <<
    “移动最后一个到前面之前的链表”;
    printList（start）;
 
    moveToFront（＆start）;
 
    cout <<
    “移除最后一个到前面后的链接列表”;
    printList（start）;
 
    返回0;
}

输出：

将最后一个到前面之前的链接列表 
1 2 3 4 5 
移除最后一个到前面后的链接列表 
5 1 2 3 4

时间复杂度： O（n），其中n是给定链接列表中的节点数。

辅助空间： O（1），因为使用常量变量