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

介绍

链表是一种常见的数据结构，它允许我们在不需要预先分配一段固定大小的内存的情况下存储和操作数据。在链表中，每个节点都由一个指向下一个节点的指针组成。可是，在某些应用场景下，我们需要重新调整链表节点的顺序，例如将最后一个元素移动到链表的开头等。因此，本文将展示如何在C++中将给定链表的最后元素移动到前面。

实现步骤

1. 基本数据结构

首先，我们需要定义链表中的节点类。节点类包含两个成员变量：节点的值和指向下一个节点的指针。

class Node {
public:
    int value; // 节点值
    Node *next; // 指向下一个节点的指针

    Node(int val) {
        value = val;
        next = nullptr;
    }
};

2. 构造链表

接下来，我们需要编写代码来构建一个包含多个节点的链表。在本文中，我们将创建一个具有以下值的链表：

1 -> 2 -> 3 -> 4 -> 5 -> nullptr

// 构造链表
Node *constructList() {
    Node *head = new Node(1);
    Node *second = new Node(2);
    Node *third = new Node(3);
    Node *fourth = new Node(4);
    Node *fifth = new Node(5);

    head->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = fifth;

    return head;
}

3. 将最后元素移动到前面

现在，我们开始编写代码将链表的最后一个元素移动到链表的开头。通常情况下，我们可以使用while循环来遍历链表并找到倒数第二个节点。接着，我们可以使用另一个指针指向最后一个节点，并将其移到链表的开头。

// 将链表的最后一个元素移动到前面
void moveLastElementToStart(Node *&head) {
    if (head == nullptr || head->next == nullptr) {
        return;
    }

    // 找到倒数第二个节点
    Node *secondLast = head;
    while (secondLast->next->next != nullptr) {
        secondLast = secondLast->next;
    }

    // 移动最后一个节点到前面
    Node *last = secondLast->next;
    secondLast->next = nullptr;
    last->next = head;
    head = last;
}

在上述代码中，我们首先判断链表是否为空或仅有一个节点，如果是，则不需要进行移动操作。接着，我们通过while循环找到链表中倒数第二个节点的位置。当我们找到倒数第二个节点后，我们可以将最后一个节点移动到链表的开头。

完整程序

#include <iostream>

using namespace std;

// 链表节点
class Node {
public:
    int value; // 节点值
    Node *next; // 指向下一个节点的指针

    Node(int val) {
        value = val;
        next = nullptr;
    }
};

// 将链表的最后一个元素移动到前面
void moveLastElementToStart(Node *&head) {
    if (head == nullptr || head->next == nullptr) {
        return;
    }

    // 找到倒数第二个节点
    Node *secondLast = head;
    while (secondLast->next->next != nullptr) {
        secondLast = secondLast->next;
    }

    // 移动最后一个节点到前面
    Node *last = secondLast->next;
    secondLast->next = nullptr;
    last->next = head;
    head = last;
}

// 构造链表
Node *constructList() {
    Node *head = new Node(1);
    Node *second = new Node(2);
    Node *third = new Node(3);
    Node *fourth = new Node(4);
    Node *fifth = new Node(5);

    head->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = fifth;

    return head;
}

// 输出链表中每个节点的值
void printList(Node *head) {
    Node *current = head;
    while (current != nullptr) {
        cout << current->value << " -> ";
        current = current->next;
    }
    cout << "nullptr" << endl;
}

int main() {
    Node *head = constructList();
    cout << "原始链表：" << endl;
    printList(head);

    moveLastElementToStart(head);
    cout << "移动后的链表：" << endl;
    printList(head);

    return 0;
}

执行结果

原始链表：
1 -> 2 -> 3 -> 4 -> 5 -> nullptr
移动后的链表：
5 -> 1 -> 2 -> 3 -> 4 -> nullptr

结论

本文展示了如何在C++中将给定链表的最后元素移动到前面。通过使用链表节点和指针以及while循环，我们可以轻松地构建，操作和输出一个链表。对于更复杂的链表操作，我们可以使用其他数据结构和算法来解决问题。