Tìm hiểu về thuật toán đảo ngược chuỗi liên kết (Linked List)

653

Bài viết được sự cho phép bởi tác giả Sơn Dương

Tiếp tục trong series thuật toán chuyên sâu, hôm nay chúng ta cùng nhau tìm hiểu một thuật toán khá phổ biến: đó là đảo ngược chuỗi liên kết đơn (Linked List).

Vẫn như mọi khi, chúng ta sử dụng Java để triển khai thuật toán.

Đảo ngược chuỗi liên kết (LinkedList)

Linked List là một cấu trúc dữ liệu được sử dụng để lưu trữ dữ liệu theo tuyến tính. Tức là từ phần tử này có thể biết được phần tiếp theo.

Mỗi phần tử của LinkedList luôn bao gồm một phần dữ liệu và địa chỉ cho phần tử tiếp theo của LinkedList.

Các phần tử LinkedList thường được gọi là các node.

Để đảo ngược một LinkedList, điều quan trọng là mình cần đảo ngược các con trỏ sao cho phần tử tiếp theo (next) trỏ đến phần tử trước đó (previous)

Sau đây là minh họa cho input và output. Mời các bạn cùng theo dõi:

Đầu vào kiểu như sau:

Đảo ngược chuỗi liên kết

Kết quả sau khi chạy thuật toán:

Đảo ngược chuỗi liên kết

Phần head của LinkedList là node đầu tiên. Không có phần tử nào có địa chỉ được lưu trữ ở vị trí này.

Phần đuôi của LikedList là node cuối cùng. Địa chỉ tiếp theo được lưu trữ ở node này là null

Có hai phương pháp để đảo ngược một danh sách liên kết đơn (Linked List)

  • Sử dụng vòng lặp
  • Sử dụng phương pháp đệ quy (recursive)

  Big O độ phức tạp thuật toán

  Thuật toán tham lam (Greedy Algorithm) – Thực hành với C++

Phương pháp dùng vòng lặp để đảo ngược một LinkedList

Để đảo ngược một LinkedList theo cách Iterative, mình cần lưu trữ các tham chiếu của phần tử next và phần tử previous, để chúng không bị mất đi khi mình hoán đổi con trỏ địa chỉ bộ nhớ sang phần tử next trong LinkedList.

Tham khảo hình minh họa dưới đây để thấy rõ hơn cách mình đảo ngược LinkedList bằng cách thay đổi các tham chiếu:

đảo ngược chuỗi liên kết (Linked List)

Cách bước thực hiện
Sau đây là các bước cần thực hiện để đảo ngược LinkedList.

Việc đầu tiên là bạn sẽ phải tạo 3 phiên bản: current, next và previous.

Lặp lại phiên bản tiếp theo cho đến khi phiên bản hiện tại không null:

  • Lưu node tiếp theo của phần tử current trong con trỏ tiếp theo.
  • Đặt node tiếp theo của current thành previous . Đây là dòng MVP.
  • Chuyển từ previous sang current.
  • Chuyển current sang next.

Cuối cùng, vì phần tử current đã đi trước phần tử cuối cùng một bậc, nên mình cần đặt phần head thành phần tử cuối cùng mà chúng ta đạt được. Điều này có sẵn trong previous.

Đặt phần đầu về previous. Do đó, mình có phần head của LinkedList mới và phần tử cuối cùng cũ hơn.

Các bước thực hiện đã rõ ràng rùi đúng không? Giờ chúng ta bắt tay vào viết code để thực hiện thuật toán đó thôi.

Đầu tiên là định nghĩa một Node.

package com.vntalking.linkedlist.reverse;

public class MyLinkedList {

    public Node head;

    public static class Node {

        Node next;

        Object data;

        Node(Object data) {

             this.data = data;
             next = null;
        }
    }
}

Tiếp theo dưới đây là chương trình Java để đảo ngược một LinkedList theo cách Iterative và hiển thị các phần tử của nó ra màn hình console:

package com.vntalking.linkedlist.reverse;

import com.vntalking.linkedlist.reverse.MyLinkedList.Node;

public class ReverseLinkedList {

    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.head = new Node(1);
        myLinkedList.head.next = new Node(2);
        myLinkedList.head.next.next = new Node(3);

        printLinkedList(myLinkedList);
        reverseLinkedList(myLinkedList);
        printLinkedList(myLinkedList);

    }

    public static void printLinkedList(MyLinkedList linkedList) {
        Node h = linkedList.head;
        while (linkedList.head != null) {
            System.out.print(linkedList.head.data + " ");
            linkedList.head = linkedList.head.next;
        }
        System.out.println();
        linkedList.head = h;
    }

    public static void reverseLinkedList(MyLinkedList linkedList) {
        Node previous = null;
        Node current = linkedList.head;
        Node next;
        while (current != null) {
            next = current.next;
            current.next = previous;
            previous = current;
            current = next;
        }
        linkedList.head = previous;
    }

}

Việc làm C++ lương cao, hấp dẫn dành cho bạn!

Đảo ngược một LinkedList bằng phương pháp đệ quy (recursive)

Trước tiên để đảo ngược một LinkList theo phương pháp đệ quy mình cần chia LinkedList thành hai phần: phần head và phần còn lại.

Ban đầu, phần head chỉ đến phần tử đầu tiên. Phần còn lại chỉ đến phần tử tiếp theo từ phần head.

Mình duyệt lần lượt các phần tử của danh sách bằng kiểu đệ quy cho đến phần tử cuối cùng thứ hai. Khi mình đã đến phần tử cuối cùng, mình đặt phần tử đó làm phần head.

Từ đó, mình thực hiện những việc những việc sau cho đến khi bắt đầu vào LinkedList.

node.next.next=node;
node.next = null;

Để không bị mất dấu vết head gốc, mình sẽ lưu một bản sao của head instance.

Bạn hãy tham khảo hình dưới đây nhé để hiểu rõ hơn nhé.

đảo ngược chuỗi liên kết (Linked List)

Bạn có thắc mắc chương trình Java đảo ngược một LinkedList theo cách đệ quy – Recursive là như thế nào không? Hãy xem chương trình Java dưới đây để hiểu rõ hơn.

public static Node recursiveReverse(Node head) {
    Node first;

    if (head==null || head.next == null)
        return head;

    first = recursiveReverse(head.next);
    head.next.next = head;
    head.next = null;

    return first;
}

Trong đoạn code trên, mình chỉ chuyển head.next trong lệnh gọi đệ quy đến phần tử cuối của LinkedList.

Khi đến cuối, mình đặt phần tử cuối cùng thứ hai làm phần tử tiếp theo của phần tử cuối cùng và đặt con trỏ tiếp theo của phần tử cuối cùng thứ hai thành Null. Phần tử cuối cùng sẽ được đánh dấu là phần head mới.

Nếu bạn muốn đảo ngược chuỗi liên kết bằng cách sử dụng phương pháp đệ quy thì hãy sử dụng mã sau:

myLinkedList.head = recursiveReverse(myLinkedList.head);

Kết quả thu được vẫn giống như cách tiếp cận sử dụng vòng lặp.

Độ phức tạp
– Time Complexity – O(n)
– Space Complexity – O(1)

Cảm ơn bạn đã theo dõi hết bài viết này. Đừng quên like và comment nhé! ❤

Bài viết gốc được đăng tải tại vntalking.com

Xem thêm:

Xem thêm It Job for Developer hấp dẫn trên TopDev