Các kiểu dữ liệu trong C ( int - float - double - char ...) 
Thuật toán tìm ước chung lớn nhất trong C/C++ 
Cấu trúc lệnh switch case trong C++ (có bài tập thực hành) 
Lệnh cin và cout trong C++ 
Random trong Python: Tạo số random ngẫu nhiên 
ComboBox - ListBox trong lập trình C# winforms 
Thuật toán kiếm tra số nguyên tố 
Cách khai báo biến trong PHP, các loại biến thường gặp 
Download và cài đặt Vertrigo Server 
Thẻ li trong HTML 
Thẻ article trong HTML5 
Cấu trúc HTML5: Cách tạo template HTML5 đầu tiên 
Cách dùng thẻ img trong HTML và các thuộc tính của img 
Thẻ a trong HTML và các thuộc tính của thẻ a thường dùng Kiểm tra danh sách liên kết đơn palindrome trong Java
Chương trình kiểm tra tính palindrome của Singly Linked List trong Java. Đây cũng là một dạng bài tập để bạn có thể hiểu hơn về Singly Linked List trong Java.
Dưới đây chúng ta sẽ thực hiện chương trình kiểm tra tính polindrome của Singly Linked List. Chương trình sẽ yêu cầu người dùng khởi tạo Singly Linked List và và kiểm tra tính chất polindrome có trong Singly Linked List.
Polindrome của Singly Linked List trong Java
Trong phần này, freetuts sẽ giúp bạn hiểu hơn về Polindrome của Singly Linked List trong Java.
Khái niệm: Polindrome là tính chất mà danh sách có chứa các phần tử có vị trí đối xứng thì đều có giá trị bằng nhau.
Bài viết này được đăng tại [free tuts .net]
Xét ví dụ sau:
- Singly Linked List cho trong hình trên là polindrome vì nó tương đương với danh sách đảo ngược của nó, tức là 1, 2, 3, 2, 1.
- Khởi tạo một biến
flag = trueđể có thể lưu vị trí sai của quá tình duyệt kiểm tra. - Để kiểm tra xem Singly Linked List có phải là một polindrome hay không, chúng ta duyệt qua Singly Linked List và kiểm tra xem có phần tử nào từ nửa bắt đầu không khớp với bất kỳ phần tử nào từ nửa kết thúc. Nếu có vị trí có giá trị không bằng thì gán
flag = false -
Nếu biến
flag = falsethì in ra màn hinh thông báo Singly Linked List không phải là polindrome. -
Nếu biến
flag = truethì in ra màn hinh thông báo Singly Linked List không là polindrome.
Để dễ hình dung hơn về thuật toán thì chúng ta hãy xem thuật toán dưới đây.
Thuật toán kiểm tra polindrome của Singly Linked List trong Java
Dưới đây là các bước chính của thuật toán trên:
Bước 1: Tạo một lớp Node có hai thuộc tính: data và next. Next là một con trỏ tới node tiếp theo trong danh sách.
Bước 2: Tạo một lớp DeleteStart có hai thuộc tính: head và tail.
Bước 3: addNode() sẽ thêm một nodemới vào danh sách:
- Tạo một node mới.
- Đầu tiên, nó kiểm tra xem head có bằng null hay không nếu bằng thì danh sách trống.
- Nếu danh sách trống, cả head và tail sẽ trỏ đến node mới được thêm vào.
- Nếu danh sách không trống, node mới sẽ được thêm vào làm tail của danh sách sao cho phần tiếp theo của tail sẽ trỏ đến một node mới được thêm vào. Node mới này sẽ trở thành tail mới của danh sách.
Bước 4: ReverseList() sẽ đảo ngược thứ tự của nút có trong danh sách:
- Node current sẽ đại diện cho một node mà danh sách cần được đảo ngược.
- Node prevNode đại diện cho node trước với node current và nextNode đại diện cho node kế tiếp của node current.
- Danh sách sẽ được đảo ngược bằng cách hoán đổi prevNode với nextNode cho mỗi node.
Bước 5: isPalindrome() sẽ kiểm tra xem danh sách đã cho có phải là palindrome hay không:
- Khai báo một node current sẽ trỏ đến node head.
- Biến flag sẽ lưu giá trị boolean true.
- Tính vị trí giữa của danh sách bằng cách chia kích thước của danh sách cho 2.
- Duyệt qua danh sách cho đến khi node current đến node giữa.
- Đảo ngược danh sách sau node giữa cho đến node tail bằng cách sử dụng
ReverseList(). Danh sách này sẽ là nửa sau của danh sách. - Bây giờ, hãy so sánh các node của nửa đầu và nửa sau của danh sách.
- Nếu bất kỳ node nào không khớp thì hãy gán
flag = falsevà ngắt vòng lặp. - Nếu
flag = truesau vòng lặp biểu thị danh sách đó là một palindrome. - Nếu
flag = falsethì danh sách không phải là một palindrome.
Bước 6: display() sẽ hiển thị các node có trong danh sách:
- Xác định node current ban đầu sẽ trỏ đến head của danh sách.
- Duyệt qua danh sách cho đến khi node current thành null.
- Hiển thị từng node bằng cách đặt con trỏ tới node next của nó trong mỗi lần lặp.
Để các bạn dễ hình dung hơn thì chúng ta bắt đầu triển khai code nhé.
Chương trình kiểm tra tính polindrome của Singly Linked List trong Java
Dưới đây là bài code mẫu cho các bạn tham khảo:
/**
* Học lập trình Java miễn phí tại freetuts.net
*
* @author freetuts
*/
public class PalindromeSinglyLinkedList {
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
public int size;
public Node head = null;
public Node tail = null;
public void addNode(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
size++;
}
public Node reverseList(Node temp) {
Node current = temp;
Node prevNode = null, nextNode = null;
while (current != null) {
nextNode = current.next;
current.next = prevNode;
prevNode = current;
current = nextNode;
}
return prevNode;
}
public void isPalindromeSinglyLinkedList() {
Node current = head;
boolean flag = true;
int mid = (size % 2 == 0) ? (size / 2) : ((size + 1) / 2);
for (int i = 1; i < mid; i++) {
current = current.next;
}
Node revHead = reverseList(current.next);
while (head != null && revHead != null) {
if (head.data != revHead.data) {
flag = false;
break;
}
head = head.next;
revHead = revHead.next;
}
if (flag) {
System.out.println("Singly linked list là một danh sách palindrome");
} else {
System.out.println("Singly linked list không phải là một palindrome");
}
}
public void display() {
Node current = head;
if (head == null) {
System.out.println("Singly linked list này trống");
return;
}
System.out.println("Các node của linked list là: ");
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
PalindromeSinglyLinkedList sList = new PalindromeSinglyLinkedList();
sList.addNode(1);
sList.addNode(2);
sList.addNode(3);
sList.addNode(2);
sList.addNode(1);
System.out.println("Chương trình này được viết tại freetuts.net");
System.out.println("");
sList.display();
sList.isPalindromeSinglyLinkedList();
}
}
Kết quả:
Như vậy chúng ta đã thực hiện xong chương trình kiểm tra tính palindrome của Singly Linked List trong Java. Chúc các bạn thực hiện thành công!!!
