Jak znaleźć środkowy element na liście linków bez przechodzenia przez całą listę?

Question

Jak znaleźć środkowy element na liście linków bez przechodzenia przez całą listę. ? ... a maksymalnie można użyć tylko 2 wskaźniki ... jak to zrobić? .... a także długość listy nie jest podana.

Answer 1

Nie widzę sposobu, w jaki można to zrobić bez przechodzenia przez całą listę, chyba że znasz długość.

Zgaduję, że odpowiedź chce, aby jeden wskaźnik przemieszczał się po jednym elemencie naraz, podczas gdy drugi wskaźnik przesunie 2 elementy naraz.
W ten sposób, gdy drugi wskaźnik osiągnie koniec, pierwszy wskaźnik znajdzie się pośrodku.

Answer 2

Poniższy kod pomoże ci uzyskać środkowy element. Musisz użyć dwóch wskaźników "szybko" i "wolno". Na każdym kroku szybki wskaźnik zwiększy się o dwa, a wolniej wzrośnie o jeden. Kiedy lista się skończy, wolny wskaźnik znajdzie się pośrodku.

rozważmy Node wygląda to

class Node 
{ 
    int data; 
    Node next; 
} 

I LinkedList ma metodę pobierająca świadczenia głowę połączonej listy

public Node getHead() 
{ 
    return this.head; 
} 

Sposób poniżej dostanie środkowy element lista (bez znajomości rozmiaru listy)

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; 
} 

przykład:
Jeżeli lista jest 1-2-3-4-5 element środkowy jest 3
Jeżeli lista jest 1-2-3-4 element środkowy jest 3

Answer 3

W C, za pomocą wskaźników, dla kompletności. Zauważ, że jest to oparte na algorytmie "Tortoise and Hare" używanym do sprawdzania, czy połączona lista zawiera cykl.

Nasz węzeł jest zdefiniowana jako następujące:

typedef struct node { 
    int   val; 
    struct node *next; 
} node_t; 

Wtedy nasz algorytm jest następujący:

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); 
} 

Listę z parzystą liczbą węzłów ta zwraca węzeł proceding rzeczywiste centrum (np. na liście 10 węzłów, to zwróci węzeł 6).

Answer 4

Istnieją dwie możliwe odpowiedzi jeden dla parzystych i jeden dla nawet, oba mają ten sam algorytm

dla nieparzystych: Jedna wskazówka przesuwa się o jeden krok i drugi wskaźnik porusza się dwa elementy w czasie i po drugie elementy osiągnąć ostatni element, element, w którym znajduje się pierwszy wskaźnik, środkowy element. Bardzo łatwe do dziwnych. Spróbuj: 1 2 3 4 5

Dla parzystego: To samo, Jeden wskaźnik przesuwa się o jeden krok, a drugi wskaźnik przesuwa dwa elementy jako czas, a gdy drugie elementy nie mogą przeskoczyć do następnego elementu, element, w którym znajduje się pierwszy wskaźnik , środkowy element. Spróbuj: 1 2 3 4

Answer 5

To głupie, aby używać dwóch wskaźników "szybko" i "wolno". Ponieważ następny operator jest używany 1,5 n razy. Nie ma optymalizacji.

Pomocne może być użycie wskaźnika do zapisania środkowego elementu.

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; 
} 

Answer 6

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); 

Answer 7

Używając zmiennej wielkości można utrzymać wielkość połączonej listy.

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; 
} 
} 

Następnie od sposobu klienta znaleźć środek wielkości listy:

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); 

} 
} 

nie wiem, czy to jest lepsze niż węzeł dwóch sposób, ale tu również nie trzeba przemierzać przez całą pętlę.

Answer 8

Korzystanie z C#, aby znaleźć środkowy element połączonej listy

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; 
    }