cách tìm nút giữa trong danh sách được liên kết đơn lẻ mà không cần truyền tải?

Question

cách tìm nút giữa trong danh sách được liên kết đơn lẻ mà không cần truyền tải?

là nó có thể ở vị trí đầu tiên?

In One traversal tôi sử dụng phương pháp truyền thống của việc sử dụng 2 con trỏ một trong đó 2 vị trí nhảy và khác một vị trí nhảy của ..is có bất kỳ phương pháp khác để tìm nút giữa trong một traversal

Answer 1

Không, nó không thể . Các địa chỉ của các nút là tùy ý, do đó, không có cách nào để biết chúng mà không đi qua chúng.

Answer 2

Có, bạn có thể nếu bạn đang kiểm soát tất cả các khía cạnh của việc thêm và xóa danh sách.

Nếu bạn duy trì tham chiếu đến những gì được coi là nút giữa chừng trong khi thêm hoặc xóa thì có thể thực hiện được. Có vài trường hợp phải được xử lý. Ngoài ra, có những tình huống như là nơi có một số nguyên tố cần xem xét. Điều gì sẽ là nút giữa chừng trong tình huống như vậy? ect .. ect ..

Vì vậy, bạn thực sự không phải là tìm nút nút ở giữa, mà đúng hơn là theo dõi nó.

Answer 3

List list = new LinkedList(); 
    for (int i = 0; i < 50; i++) { 
    list.add(String.valueOf(i)); 
} 

int end = list.size() - 1; 
int start = 0; 
while (start > end) { 
    start++; 
    end--; 
} 
if(start == end) //The arrays length is an odd number and you found the middle 
    return start; 
else //The arrays length is an even number and there really isn't a middle 
    //Do something else here because you have an even number 

Tôi thấy mã này trên một số trang giải pháp khác ... Đây có phải là phương pháp khác mà danh sách đang được duyệt qua một lần không !?

Answer 4

import java.util.LinkedList; 
import java.util.List; 


public class consoleApp 
{ 
    public static void main(String[] args) 
    { 
     List list = new LinkedList(); 
     for (int i = 0; i < 50; i++) 
     { 
      list.add(String.valueOf(i)); 
     } 

     int end = list.size(); 

     int start = 0; 
     while (start< end) 
     { 
      start++; 
      end--; 
     } 

     if(start == end) 
      System.out.println(start); 
    } 
} 

Answer 5

public void findMiddleNode() { 
    Node n1 = headNode; 
    Node n2 = headNode; 
    while(n2.getNext() != null && n2.getNext().getNext()!= null) { 
     n1 = n1.getNext(); 
     n2 = n2.getNext().getNext(); 
    } 

    System.out.println("middle node is "+n1.getKey()); 
}