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

0
Bài này thuộc phần 6 của 7 phần trong series Thuật toán chuyên sâu

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.

Với mỗi phần tử của LinkedList 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ử next trỏ đến phần tử 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:

linkedlist-reverse-input

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

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)

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.

😘 Đọc bài viết về thuật toán:

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;
    }

}

Đả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 mất dấu vết của head gốc, mình sẽ lưu một bản sao của head instance.

Để hiểu hơn về quy trình trên, bạn hãy tham khảo hình dưới đây 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 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 chương trình trên mình chỉ chuyển head.next trong lệnh gọi đệ quy để đi đến phần tử cuối của LinkedList.

Khi mình đế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é! ❤

Xem tiếp các bài trong Series
Phần trước: Thuật toán Level Order Traversal (LOT) hay Breadth First Traversal (BFT) để duyệt treePhần kế tiếp: Thuật toán tìm kiếm nhị phân – Binary Search Tree (BTS)
Dịch vụ phát triển ứng dụng mobile giá rẻ - chất lượng

Bình luận. Cùng nhau thảo luận nhé!

avatar
  Theo dõi bình luận  
Thông báo