Cách tìm phần tử ở giữa trong danh sách liên kết mà không phải duyệt qua toàn bộ danh sách. ? ... và tối đa bạn chỉ có thể sử dụng 2 con trỏ ... làm thế nào để làm? .... và chiều dài của danh sách không được đưa ra.Làm thế nào để Tìm một phần tử ở giữa trong danh sách liên kết mà không vượt qua toàn bộ danh sách?
Tôi không thấy cách bạn có thể thực hiện điều đó mà không vượt qua toàn bộ danh sách trừ khi bạn biết độ dài.
Tôi đoán câu trả lời muốn một con trỏ di chuyển ngang qua một phần tử tại một thời điểm, trong khi con trỏ thứ hai di chuyển 2 phần tử cùng một lúc.
Bằng cách này khi con trỏ thứ hai đến cuối, con trỏ đầu tiên sẽ ở giữa.
Mã bên dưới sẽ giúp bạn lấy phần tử ở giữa. Bạn cần sử dụng hai con trỏ "nhanh" và "chậm". Ở mỗi bước, con trỏ nhanh sẽ tăng lên hai và chậm hơn sẽ tăng thêm một. Khi danh sách sẽ kết thúc con trỏ chậm sẽ ở giữa.
Chúng ta hãy xem xét các Node trông như thế này
class Node
{
int data;
Node next;
}
Và LinkedList có một phương thức getter để cung cấp người đứng đầu danh sách liên kết
public Node getHead()
{
return this.head;
}
Các phương pháp dưới đây sẽ nhận được các yếu tố giữa danh sách (Không biết kích thước của danh sách)
public int getMiddleElement(LinkedList l)
{
return getMiddleElement(l.getHead());
}
private int getMiddleElement(Node n)
{
Node slow = n;
Node fast = n;
while(fast!=null && fast.next!=null)
{
fast = fast.next.next;
slow = slow.next;
}
return slow.data;
}
Ví dụ:
Nếu danh sách là 1-2-3-4-5 các yếu tố giữa là 3
Nếu danh sách là 1-2-3-4 các yếu tố giữa là 3
Trong C, sử dụng con trỏ, để hoàn thành. Lưu ý rằng điều này dựa trên thuật toán "Tortoise and Hare" được sử dụng để kiểm tra xem danh sách được liên kết có chứa chu trình hay không.
nút của chúng tôi được xác định như sau:
typedef struct node {
int val;
struct node *next;
} node_t;
Sau đó, thuật toán của chúng tôi là như sau:
node_t *
list_middle (node_t *root)
{
node_t *tort = root;
node_t *hare = root;
while (hare != NULL && hare->next != NULL) {
tort = tort->next;
hare = hare->next->next;
}
return (tort);
}
Đối với một danh sách với một số chẵn các nút này sẽ trả về nút proceding trung tâm thực tế (ví dụ trong danh sách 10 nút, điều này sẽ trả về nút 6).
Có hai câu trả lời có thể một cho lẻ và một cho thậm chí, cả hai có cùng một thuật toán
Đối lẻ: Một con trỏ di chuyển một bước và con trỏ thứ hai di chuyển hai yếu tố là thời gian và khi các yếu tố thứ hai đạt được phần tử cuối cùng, phần tử mà con trỏ đầu tiên là phần tử ở giữa. Rất dễ dàng cho kỳ quặc. Thử: 1 2 3 4 5
Đối với chẵn: Một con trỏ di chuyển một bước và con trỏ thứ hai di chuyển hai phần tử thành thời gian và khi phần tử thứ hai không thể nhảy đến phần tử tiếp theo, phần tử mà con trỏ đầu tiên , phần tử giữa. Thử: 1 2 3 4
Thật ngu xuẩn khi sử dụng hai con trỏ "nhanh" và "chậm" .Bởi vì nhà điều hành tiếp theo được sử dụng 1,5 lần. Không có tối ưu hóa.
Sử dụng con trỏ để lưu phần tử ở giữa có thể giúp bạn.
list* find_mid_1(list* ptr)
{
list *p_s1 = ptr, *p_s2 = ptr;
while (p_s2=p_s2->get_next())
{
p_s2 = p_s2->get_next();
if (!p_s2)
break;
p_s1 = p_s1->get_next();
}
return p_s1;
}
LinkedList.Node current = head;
int length = 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);
Sử dụng một biến kích thước mà bạn có thể duy trì kích thước của danh sách liên kết.
public class LinkedList {
private Node headnode;
private int size;
public void add(int i){
Node node = new Node(i);
node.nextNode = headnode;
headnode = node;
size++;
}
public void findMiddleNode(LinkedList linkedList, int middle) {
Node headnode = linkedList.getHeadnode();
int count = -1;
while (headnode!=null){
count++;
if(count == middle){
System.out.println(headnode.data);
}else {
headnode = headnode.nextNode;
}
}
}
private class Node {
private Node nextNode;
private int data;
public Node(int data) {
this.data = data;
this.nextNode = null;
}
}
public Node getHeadnode() {
return headnode;
}
public int getSize() {
return size;
}
}
Sau đó, từ một phương pháp khách hàng tìm thấy giữa kích thước của danh sách:
public class MainLinkedList {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.add(5);
linkedList.add(3);
linkedList.add(9);
linkedList.add(4);
linkedList.add(7);
linkedList.add(99);
linkedList.add(34);
linkedList.add(798);
linkedList.add(45);
linkedList.add(99);
linkedList.add(46);
linkedList.add(22);
linkedList.add(22);
System.out.println(linkedList.getSize());
int middle = linkedList.getSize()/2;
linkedList.findMiddleNode(linkedList, middle);
}
}
Tôi không biết nếu điều này là tốt hơn so với nút hai chiều, nhưng ở đây cũng có thể bạn không cần phải đi qua thông qua toàn bộ vòng lặp.
Sử dụng C# để tìm thấy một yếu tố giữa của danh sách liên kết
static void Main(string[] args)
{
LinkedList<int> linked = new LinkedList<int>();
linked.AddLast(1);
linked.AddLast(3);
linked.AddLast(5);
linked.AddLast(6);
linked.AddFirst(12);
Console.WriteLine("Middle Element - "+ListMiddle<int>(linked));
Console.ReadLine(); }
public static T ListMiddle<T>(IEnumerable<T> input)
{
if (input == null)
return default(T);
var slow = input.GetEnumerator();
var fast = input.GetEnumerator();
while (slow.MoveNext())
{
if (fast.MoveNext())
{
if (!fast.MoveNext())
return slow.Current;
}
else
{
return slow.Current;
}
}
return slow.Current;
}
NHƯNG Tôi muốn xem nó hoạt động cho cả số lẻ và chẵn số phần tử trong một danh sách liên kết ...? – RAM
Hãy dùng thử trên giấy cho 1,2,3,4,5 phần tử - bạn sẽ nhận thấy một mẫu và cách thức/tại sao nó hoạt động –