Thuật Toán đảo Ngược Chuỗi Liên Kết (Linked List) - VNTALKING

Bài này thuộc phần 5 của 12 phần trong series Cấu trúc dữ liệu và giải thuật

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.

Nội dung chính của bài viết

• Đảo ngược chuỗi liên kết (LinkedList)
  • Phương pháp dùng vòng lặp để đảo ngược một LinkedList
  • Đảo ngược một LinkedList bằng phương pháp đệ quy (recursive)

Đả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:

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:

• Bài toán tháp Hà Nội – Thuật toán và cách giải
• 5 thuật toán mà mọi lập trình viên nên biết
• Thuật toán trong lập trình – Đôi điều tản mạ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:

Cách bước thực hiệnSau đâ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 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é.

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é! ❤

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: Thực hành cài đặt và sử dụng Hàng đợi – Queue trong C++