kết quả từ 1 tới 5 trên 5

Bài tập về danh sách liên kết đơn

  1. #1
    Ðến Từ
    Cà Mau
    Thành Viên Thứ: 368053
    Bài gửi
    4

    Question Bài tập về danh sách liên kết đơn

    a) Cho một danh sách liên kết đơn gồm N phần tử (N < 10000000). Viết hàm in ra phần tử thứ N/2 của dãy.
    Mã:
    int phan_tu_n2(Node * ds)
    b) Cho một danh sách liên kết đơn gồm N phần tử (N < 10000000), có thể không phải là danh sách trong câu a, và một số nguyên không âm K (K < N). Viết hàm in ra phần tử thứ K tính từ cuối dãy. Lưu ý K = 0 là phần tử cuối dãy, K = N - 1 là phần tử đầu dãy.
    Mã:
    int phan_tu_k_tu_cuoi(Node * ds, int k)
    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    Cà Mau
    Thành Viên Thứ: 368053
    Bài gửi
    4

    Reply: Bài tập về danh sách liên kết đơn

    Ai viết giúp em với.

  3. #3
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Bài tập về danh sách liên kết đơn

    Mình đang đi nghỉ lễ nên chỉ gợi ý thế này.
    - Câu a dùng 2 pointers, một pointer chạy từng phần tử, một pointer chạy nhanh gấp đôi.
    - Câu b dùng 2 pointers, một pointer đi trước K phần tử.
    Nếu bạn cần code thì sau khi mình về mới viết đc.
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  4. Đã cảm ơn tengiday:


  5. #4
    Ðến Từ
    Cà Mau
    Thành Viên Thứ: 368053
    Bài gửi
    4

    Reply: Bài tập về danh sách liên kết đơn

    Cám ơn bác. Bao giờ bác về viết giúp em đoạn code. Em còn 1 bài nữa: cho một danh sách liên kết đơn. Tìm node có phần tử bắt đầu chu trình. Ví dụ 1->2->3->4->5. Sau đó con trỏ của 5 chỉ ngược lại node chứa 2. Như vậy kết quả là node chứa 2. Nếu không có chu trình thì trả ra null.
    Mã:
     Node * node_bat_dau_chu_trinh(Node * head)

  6. Đã cảm ơn SvNgheo01:


  7. #5
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Bài tập về danh sách liên kết đơn

    Câu a: Bạn dùng 2 pointers như thế này là được.
    Mã:
    if (ds) {
        Node * walker = ds;
        Node * runner = ds;
        while (runner->next && runner->next->next) {
            walker = walker->next;
            runner = runner->next->next;
        }
            return walker;
    }
    return 0;
    Câu b:
    Mã:
    Node * last = ds;
    for (int i = 0; last && i < k; last = last->next, ++i);
    for (Node * i = ds; last; last = last->next, i = i->next)
        if (!last->next)
            return i;
    return 0;
    Bài tìm node bắt đầu chu trình: Bài này tư tưởng tương tự như dùng 2 pointers vậy: một nhanh, một chậm. Nếu có cycle thì phải gặp nhau trong cycle. Còn riêng node bắt đầu chu trình thì giải thích như sau:
    Mã:
    Giả sử có linked list với node E là cycle entry và X là node mà 2 pointers bắt kịp nhau ở trong cycle. Gọi:
    - H: khoảng cách từ head tới E.
    - D: khoảng cách từ E tới X.
    - L: cycle length.
                     _____
                    /     \
    head_____H______E      \
                    \      /
                     X____/
    Tại X, walker đã đi đc quãng đg` là H + D, còn faster đi đc quãng đg` là 2(H + D). Nếu faster đã đi quanh cycle đc n vòng thì ta có:
    2H + 2D = H + D + nL, so H + D = nL, H = nL - D.
    Bởi vậy, sau khi biết đc có chu trình, cho 2 pointers chạy: một từ head, một từ X thì 2 pointers này phải gặp nhau ở E.
    Mã:
    if (head == 0) return 0;
    ListNode * walker = head, * runner = head;
    bool hasCycle = 0;
    while (runner->next != 0 && runner->next->next != 0) {
        walker = walker->next;
        runner = runner->next->next;
        if (walker == runner) {
            hasCycle = 1;
            break;
        }
    }
    if (!hasCycle) return 0;
    while (head != walker) {
        head = head->next;
        walker = walker->next;
    }
    return head;

  8. Đã cảm ơn tengiday: