как пройти середину единственно связанного списка за одну итерацию?

Question

Недавно мне задали один вопрос, который в единственно связанном списке, как нам перейти к середине списка за одну итерацию.

A --> B --> C --> D (even nodes)

для этого он должен вернуть адрес, который указывает на B

A --> B --> C (odd nodes)

для этого также должен возвращать адрес, который указывает на B

Существует одно решение - взять два указателя, один ход один раз, а другой - два раза, но здесь это не похоже.

LinkedList p1,p2;

while(p2.next != null)
{
    p1 = p1.next;
    p2 = p2.next.next;

}

System.out.print("middle of the node" + p1.data); //This does not give accurate result in odd and even

Пожалуйста, помогите, если кто-то делал это раньше.

Answer 1

Основной алгоритм будет

0 Взять два указателя

1 Сделать так, чтобы оба указывали на первый узел

2 Увеличивается сначала с двумя узлами и сначала, если он успешен, затем перемещается со второго на один узел вперед

3 когда второй конец дойдет до конца, первый окажется посередине.

Обновление:

Это определенно будет работать в нечетном случае, для четного случая вам нужно проверить еще одно условие, если первая точка может двигаться далее , но не рядом со следующим тогда оба указателя будут посередине, вам нужно решить, какой из них взять в качестве среднего

Answer 2

Вы не можете продвинуться по p1, если вы не успешно продвинулись по p2 дважды;в противном случае длина списка равна 2, и оба конца указывают на конец (и вы указали, что списки четной длины должны округляться к началу).

Итак:

while ( p2.next != null ) {
    p2 = p2.next;
    if (p2.next != null) {
        p2 = p2.next;
        p1 = p1.next;
    }
}

Answer 3

Я знаю, что вы уже приняли ответ, но весь этот вопрос звучит скорее как упражнение с умом, а не как попытка найти правильное решение.Зачем вам делать что-то в O (n), если вы можете сделать это в O (n / 2)?

РЕДАКТИРОВАТЬ: Это используется для подтверждения производительности O (1), и это просто не правильно.Спасибо ysth за указание на это.

На практике вы бы делали это за ноль итераций:

LinkedList list = ...
int size = list.size();
int middle = (size / 2) + (size % 2 == 0 ? 0 : 1) - 1; //index of middle item
Object o = list.get(middle);  //or ListIterator it = list.listIterator(middle);

Answer 4

public static Node middle(Node head){

    Node slow=head,fast=head;
    while(fast!=null& fast.next!=null && fast.next.next!=null){

         slow=slow.next;
         fast=fast.next.next;                   
    } 


    if(fast!=null && fast.next!=null){
        slow=slow.next;
    }


    return slow;

} 

Answer 5

static ListElement findMiddle(ListElement head){
    ListElement slower = head;
    ListElement faster = head;
    while(faster.next != null && faster.next.next !=null ){
        faster = faster.next.next;
        slower = slower.next;
    } 
    return slower;
}

Answer 6

Решение взять два указателя и один ход в половину скорости должно работать нормально. Скорее всего, проблема не в решении, а в фактической реализации. Опубликуйте больше деталей вашей реализации.