Đảo ngược danh sách được liên kết trong Java

1. Giới thiệu

Trong hướng dẫn này, chúng tôi sẽ triển khai hai thuật toán đảo ngược danh sách liên kết trong Java.

2. Cấu trúc dữ liệu danh sách được liên kết

Danh sách được liên kết là một cấu trúc dữ liệu tuyến tính, trong đó một con trỏ trong mỗi phần tử xác định thứ tự. Mỗi phần tử của danh sách được liên kết chứa một trường dữ liệu để lưu trữ dữ liệu danh sách và một trường con trỏ để trỏ đến phần tử tiếp theo trong chuỗi. Ngoài ra, chúng ta có thể sử dụng một đầu con trỏ để trỏ đến các yếu tố khởi đầu của một danh sách liên kết:

Sau khi chúng tôi đảo ngược danh sách được liên kết, phần đầu sẽ trỏ đến phần tử cuối cùng của danh sách được liên kết ban đầu và con trỏ của mỗi phần tử sẽ trỏ đến phần tử trước đó của danh sách được liên kết ban đầu:

Trong Java, chúng tôi có một lớp LinkedList để cung cấp triển khai danh sách được liên kết kép của các giao diện ListDeque . Tuy nhiên, chúng tôi sẽ sử dụng cấu trúc dữ liệu danh sách được liên kết riêng trong hướng dẫn này.

Trước tiên, hãy bắt đầu với một lớp ListNode để đại diện cho một phần tử của danh sách được liên kết:

public class ListNode { private int data; private ListNode next; ListNode(int data) { this.data = data; this.next = null; } // standard getters and setters }

Lớp ListNode có hai trường:

  • Một giá trị số nguyên để biểu thị dữ liệu của phần tử
  • Một con trỏ / tham chiếu đến phần tử tiếp theo

Một danh sách được liên kết có thể chứa nhiều đối tượng ListNode . Ví dụ: chúng ta có thể xây dựng danh sách liên kết mẫu ở trên bằng một vòng lặp:

ListNode constructLinkedList() { ListNode head = null; ListNode tail = null; for (int i = 1; i <= 5; i++) { ListNode node = new ListNode(i); if (head == null) { head = node; } else { tail.setNext(node); } tail = node; } return head; }

3. Thực hiện thuật toán lặp lại

Hãy triển khai thuật toán lặp trong Java:

ListNode reverseList(ListNode head) { ListNode previous = null; ListNode current = head; while (current != null) { ListNode nextElement = current.getNext(); current.setNext(previous); previous = current; current = nextElement; } return previous; }

Trong thuật toán lặp này, chúng tôi sử dụng hai biến ListNode , trước đóhiện tại , để biểu diễn hai phần tử liền kề trong danh sách liên kết. Đối với mỗi lần lặp, chúng tôi đảo ngược hai phần tử này và sau đó chuyển sang hai phần tử tiếp theo.

Cuối cùng, con trỏ hiện tại sẽ là null và con trỏ trước đó sẽ là phần tử cuối cùng của danh sách liên kết cũ. Do đó, trước đó cũng là con trỏ tiêu đề mới của danh sách liên kết bị đảo ngược và chúng tôi trả về nó từ phương thức.

Chúng tôi có thể xác minh việc triển khai lặp đi lặp lại này bằng một bài kiểm tra đơn vị đơn giản:

@Test public void givenLinkedList_whenIterativeReverse_thenOutputCorrectResult() { ListNode head = constructLinkedList(); ListNode node = head; for (int i = 1; i <= 5; i++) { assertNotNull(node); assertEquals(i, node.getData()); node = node.getNext(); } LinkedListReversal reversal = new LinkedListReversal(); node = reversal.reverseList(head); for (int i = 5; i>= 1; i--) { assertNotNull(node); assertEquals(i, node.getData()); node = node.getNext(); } }

Trong bài kiểm tra đơn vị này, trước tiên chúng tôi xây dựng một danh sách liên kết mẫu với năm nút. Ngoài ra, chúng tôi xác minh rằng mỗi nút trong danh sách được liên kết chứa giá trị dữ liệu chính xác. Sau đó, chúng ta gọi hàm lặp để đảo ngược danh sách liên kết. Cuối cùng, chúng tôi kiểm tra danh sách liên kết bị đảo ngược để đảm bảo dữ liệu được đảo ngược như mong đợi.

4. Thực hiện thuật toán đệ quy

Bây giờ, hãy triển khai thuật toán đệ quy trong Java:

ListNode reverseListRecursive(ListNode head) { if (head == null) { return null; } if (head.getNext() == null) { return head; } ListNode node = reverseListRecursive(head.getNext()); head.getNext().setNext(head); head.setNext(null); return node; }

Trong hàm reverseListRecursive , chúng tôi truy cập đệ quy từng phần tử trong danh sách được liên kết cho đến khi chúng tôi đến phần tử cuối cùng. Phần tử cuối cùng này sẽ trở thành phần đầu mới của danh sách liên kết đảo ngược. Ngoài ra, chúng tôi nối phần tử đã truy cập vào cuối danh sách liên kết được đảo ngược một phần.

Tương tự, chúng ta có thể xác minh việc triển khai đệ quy này bằng một bài kiểm tra đơn vị đơn giản:

@Test public void givenLinkedList_whenRecursiveReverse_thenOutputCorrectResult() { ListNode head = constructLinkedList(); ListNode node = head; for (int i = 1; i <= 5; i++) { assertNotNull(node); assertEquals(i, node.getData()); node = node.getNext(); } LinkedListReversal reversal = new LinkedListReversal(); node = reversal.reverseListRecursive(head); for (int i = 5; i>= 1; i--) { assertNotNull(node); assertEquals(i, node.getData()); node = node.getNext(); } }

5. Kết luận

Trong hướng dẫn này, chúng tôi đã triển khai hai thuật toán để đảo ngược danh sách được liên kết. Như mọi khi, mã nguồn của bài viết có sẵn trên GitHub.