หาโหนด Kth จากท้ายใน Singly Linked List ที่กำหนดโดยใช้ C++

Linked list เป็นโครงสร้างข้อมูลเชิงเส้นที่มีโหนดหลายตัวที่เชื่อมต่อกัน แต่ละโหนดประกอบด้วยสองฟิลด์ คือ Data Field และที่อยู่ของโหนดถัดไป สมมติว่าเรามี singly linked list งานคือหาโหนด Kth จากท้ายใน singly linked list ที่กำหนด ตัวอย่างเช่น

อินพุต

1 → 2 → 3 → 4 → 7 → 8 → 9, K = 4

เอาต์พุต

Node from the 4th Position is - 4

คำอธิบาย

เนื่องจากใน singly linked list ที่กำหนด โหนด '4th' จากท้ายคือ '4' เราจะคืนค่าเอาต์พุตเป็น '4'

วิธีการแก้ปัญหา

เริ่มต้นเรามี linked list ที่ประกอบด้วยโหนด แต่ละโหนดมีข้อมูลและที่อยู่ไปยังโหนดถัดไป ดังนั้น เพื่อหาโหนด Kth จากท้าย เราจะใช้ตัวชี้สองตัวซึ่งเริ่มต้นชี้ไปที่ head ของ linked list

ขณะวนลูปผ่าน linked list เราจะเลื่อนตัวชี้หนึ่งตัว ให้เรียกว่า 'fast' และจากนั้นเลื่อนอีกตัวชี้หนึ่งจนกว่า 'fast' pointer จะถึงท้าย

• ฟังก์ชัน kthNodefromTheEnd(node* head, int pos) รับ pointer ไปยังโหนด head และตำแหน่งเป็นพารามิเตอร์และคืนค่าโหนดจากท้าย
• ให้ตัวชี้สองตัว 'slow' และ 'fast' ซึ่งเริ่มต้นอยู่ที่ head
• วนลูปผ่าน linked list และเลื่อน fast pointer
• เนื่องจาก 'fast' pointer อยู่ข้างหน้า 'slow' สองขั้นตอน ให้เราเลื่อนตัวชี้ทั้งสองจนกว่า 'fast' จะถึงท้าย
• ตอนนี้คืนค่าที่ slow ซึ่งชี้ไปที่โหนด Kth จากท้าย

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int d) {
        data = d;
        next = NULL;
    }
};

void insertAtHead(Node* &head, int d) {
    Node* n = new Node(d);
    n->next = head;
    head = n;
}

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

void kthFromTheEnd(Node* head, int k) {
    Node* slow = head;
    Node* fast = head;
    
    for (int i = 0; i < k; i++) {
        fast = fast->next;
    }
    
    while (fast != NULL) {
        slow = slow->next;
        fast = fast->next;
    }
    
    cout << "Node from the " << k << "th position is " << slow->data << endl;
}

int main() {
    Node* head = NULL;
    insertAtHead(head, 2);
    insertAtHead(head, 4);
    insertAtHead(head, 5);
    insertAtHead(head, 6);
    insertAtHead(head, 7);
    printList(head);
    cout << endl;
    kthFromTheEnd(head, 4);
    return 0;
}

ผลลัพธ์

การรันโค้ดด้านบนจะสร้างเอาต์พุตเป็น

Node from the 4th position is: 6

คำอธิบาย - Linked list ที่กำหนดคือ 7 → 6 → 5 → 4 → 2 → และค่า kth คือ '4' ดังนั้น โหนด 4th จากท้ายคือ '6' ดังนั้นเราจะคืนค่า '6'