Làm thế nào để tìm một phần tử ở giữa trong một mảng liên kết đơn chỉ trong một lần tìm là một câu hỏi lập trình thường được hỏi các lập trình viên Java. Câu hỏi này tương tự như kiểm tra về tính giai thừa, trong đó Người phỏng vấn đôi khi cũng yêu cầu viết code. Để trả lời câu hỏi này, ứng viên phải làm quen với cấu trúc dữ liệu Danh sách liên kết tức là Trong trường hợp của Danh sách liên kết, mỗi nút của Danh sách liên kết chứa dữ liệu và con trỏ, là địa chỉ của Danh sách liên kết và phần tử cuối cùng của Danh sách liên kết một cách đơn lẻ. Liệt kê các điểm về phía các liên kết rỗng. Vì để tìm phần tử giữa của Danh sách liên kết, bạn cần phải tìm độ dài của danh sách được liên kết, tức là tính các phần tử cho đến cuối, cho đến khi bạn tìm thấy phần tử cuối cùng của Danh sách liên kết.
Điều làm cho cấu trúc dữ liệu này trở nên thú vị Câu hỏi phỏng vấn là bạn cần tìm phần tử chính giữa của Danh sách liên kết trong một lần chuyển và bạn không biết độ dài của Danh sách liên kết.
Đây là nơi mà khả năng logic của ứng viên được đưa vào bài kiểm tra, cho dù anh ta có quen với việc đánh đổi không gian và thời gian hay không, v.v.
Nếu bạn suy nghĩ cẩn thận, bạn có thể giải quyết vấn đề này bằng cách sử dụng hai con trỏ như đã đề cập trong bài đăng cuối cùng của tôi về Cách tìm độ dài của Danh sách liên kết đơn trong Java.
Bằng cách sử dụng hai con trỏ, tăng một con trỏ ở mỗi lần lặp và con trỏ khác ở mỗi lần lặp thứ hai. Khi con trỏ đầu tiên trỏ đến cuối Danh sách liên kết, con trỏ thứ hai sẽ trỏ đến một nút giữa của Danh sách liên kết.
Trên thực tế, phương pháp tiếp cận hai con trỏ này có thể giải quyết nhiều vấn đề tương tự như cách tìm nút thứ ba từ cuối cùng trong Danh sách liên kết trong một Lặp lại hoặc cách tìm phần tử thứ N từ cuối cùng trong Danh sách liên kết. Trong hướng dẫn lập trình Java này, chúng ta sẽ thấy một chương trình Java tìm thấy phần tử giữa của Danh sách Liên kết trong một lần Lặp lại.
Cách tìm phần tử giữa của LinkedList trong một lần vượt qua
Đây là một chương trình Java hoàn chỉnh để tìm nút giữa của Danh sách liên kết trong Java. Hãy nhớ lớp Danh sách liên kết ở đây là lớp tùy chỉnh của chúng tôi và đừng nhầm lẫn lớp này với java.util.LinkedList là một lớp Collection phổ biến trong Java.
Trong chương trình Java này, lớp LinkedList của chúng ta đại diện cho một cấu trúc dữ liệu danh sách liên kết chứa một tập hợp các nút và có phần đầu và phần đuôi.
Mỗi nút chứa phần dữ liệu và địa chỉ. Phương thức chính của lớp LinkedListTest được sử dụng để mô phỏng vấn đề, trong đó chúng tôi đã tạo Danh sách liên kết và thêm một số phần tử trên đó rồi lặp lại chúng để tìm phần tử giữa của danh sách được liên kết trong một lần truyền trong Java.
Chương trình Java để tìm một phần tử ở giữa trong một mảng liên kết đơn chỉ trong một lần tìm
import java.io.IOException; import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; import java.util.LinkedHashMap; import java.util.List; import java.util.Map; import java.util.Map.Entry; import java.util.Set; import test.LinkedList.Node; /** *Java program to find middle element of linked list in one pass. * In order to find middle element of a linked list * we need to find the length first but since we can only * traverselinked listone time, we will have to use two pointers * one which we will increment on each iteration while * other which will be incremented every second iteration. * So when the first pointer will point to the end of a * linked list, second will be pointing to the middle * element of a linked list * * @author Javin Paul */ publicclassLinkedListTest{ publicstaticvoidmain[Stringargs[]]{ //creating LinkedList with 5 elements including head LinkedListlinkedList =newLinkedList[]; LinkedList.Nodehead = linkedList.head[]; linkedList.add[newLinkedList.Node["1"]]; linkedList.add[newLinkedList.Node["2"]]; linkedList.add[newLinkedList.Node["3"]]; linkedList.add[newLinkedList.Node["4"]]; //finding middle element of LinkedList in single pass LinkedList.Nodecurrent = head; intlength =0; LinkedList.Node middle = head; while[current.next[]!=null]{ length++; if[length%2 ==0]{ middle = middle.next[]; } current = current.next[]; } if[length%2 == 1]{ middle = middle.next[]; } System.out.println["length of LinkedList: "+ length]; System.out.println["middle element of LinkedList : " + middle]; } } classLinkedList{ privateNodehead; privateNode tail; publicLinkedList[]{ this.head=newNode["head"]; tail = head; } publicNodehead[]{ returnhead; } publicvoidadd[Nodenode]{ tail.next= node; tail = node; } publicstaticclassNode{ privateNodenext; privateStringdata; publicNode[Stringdata]{ this.data= data; } publicStringdata[]{ returndata; } publicvoidsetData[Stringdata]{ this.data= data; } publicNodenext[]{ returnnext; } publicvoidsetNext[Nodenext]{ this.next= next; } publicStringtoString[]{ returnthis.data; } } } Output: length of LinkedList: 4 the middle element of LinkedList: 2Đó là tất cả về Cách tìm phần tử giữa của LinkedList trong một lần chuyển. Như tôi đã nói, đây là một câu hỏi phỏng vấn tốt để tách biệt lập trình viên với những người không phải lập trình viên. Ngoài ra, kỹ thuật được đề cập ở đây để tìm nút giữa của LinkedList cũng có thể được sử dụng để tìm phần tử thứ 3 từ phần tử Cuối cùng hoặc phần tử thứ n từ cuối cùng trong một LinkedList.
Nguồn: //javarevisited.blogspot.com/2012/12/how-to-find-middle-element-of-linked-list-one-pass.html#axzz70P0Balrg