Di chuyển nút cuối về đầu danh sách liên kết C++

Cho danh sách liên kết đơn, di chuyển nút cuối cùng lên làm nút đầu (head).

Ví dụ

Input: 1→2→3→4→5→NULL
Output: 5→1→2→3→4→NULL

Thuật toán

• Nếu rỗng hoặc 1 nút → trả về.
• Tìm nút cuối (last) và nút倒数第二 (secondLast).
• secondLast->next = NULL.
• last->next = head.
• head = last.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

struct Node { int data; Node* next; };

void moveLastToFront(Node** head) {
    if (!*head || !(*head)->next) return;
    Node *secondLast = *head, *last = *head;
    while (last->next) {
        secondLast = last;
        last = last->next;
    }
    secondLast->next = nullptr;
    last->next = *head;
    *head = last;
}

void push(Node** head, int data) {
    Node* n = new Node{data, *head};
    *head = n;
}

void printList(Node* head) {
    while (head) { cout << head->data << "->"; head = head->next; }
    cout << "NULL" << endl;
}

int main() {
    Node* head = nullptr;
    for (int i = 9; i >= 1; i--) push(&head, i); // 1->2->...->9
    moveLastToFront(&head);
    printList(head); // 9->1->2->...->8->NULL
    return 0;
}

Kết quả

9->1->2->3->4->5->6->7->8->NULL