ย้ายองค์ประกอบสุดท้ายไปหน้าสุดของลิงก์ลิสต์ที่กำหนดใน C++

โจทย์

ได้รับลิงก์ลิสต์ เราต้องย้ายองค์ประกอบสุดท้ายไปหน้าสุด มาดูตัวอย่างกัน

อินพุต

1 -> 2 -> 3 -> 4 -> 5 -> NULL

เอาต์พุต

5 -> 1 -> 2 -> 3 -> 4 -> NULL

อัลกอริธึม

• กำหนดลิงก์ลิสต์
• คืนค่าถ้าลิงก์ลิสต์ว่างหรือมีโหนดเดียว
• หาโหนดสุดท้ายและโหนดรองสุดท้ายของลิงก์ลิสต์
• ทำให้โหนดสุดท้ายเป็นหัวใหม่
• อัปเดตลิงก์ของโหนดรองสุดท้าย

การนำไปใช้งาน

ต่อไปนี้เป็นการนำไปใช้งานของอัลกอริธึมข้างต้นใน C++

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

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

void moveFirstNodeToEnd(struct Node** head) { 
    if (*head == NULL || (*head)->next == NULL) { 
        return; 
    } 
    struct Node* secondLastNode = *head; 
    struct Node* lastNode = *head; 
    while (lastNode->next != NULL) { 
        secondLastNode = lastNode; 
        lastNode = lastNode->next; 
    } 
    secondLastNode->next = NULL; 
    lastNode->next = *head; 
    *head = lastNode; 
} 

void addNewNode(struct Node** head, int new_data) { 
    struct Node* newNode = new Node; 
    newNode->data = new_data; 
    newNode->next = *head; 
    *head = newNode; 
} 

void printLinkedList(struct Node* node) { 
    while (node != NULL) { 
        cout << node->data << "->"; 
        node = node->next; 
    } 
    cout << "NULL" << endl; 
} 

int main() { 
    struct Node* head = NULL; 
    addNewNode(&head, 1); 
    addNewNode(&head, 2); 
    addNewNode(&head, 3); 
    addNewNode(&head, 4); 
    addNewNode(&head, 5); 
    addNewNode(&head, 6); 
    addNewNode(&head, 7); 
    addNewNode(&head, 8); 
    addNewNode(&head, 9); 
    moveFirstNodeToEnd(&head); 
    printLinkedList(head); 
    return 0; 
}

ผลลัพธ์

หากคุณรันโค้ดข้างต้น คุณจะได้ผลลัพธ์ดังนี้

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