Найти третий последний элемент в единственном списке ссылок — Алгоритм

Вопрос:

Я думаю, что Алго найдет третий последний элемент в списке единственных ссылок, и я придумаю один из них (пространство неэффективно)
Поместите список ссылок в ArrayList, используя цикл с временной сложностью O (n) [много сложностей в пространстве]
затем найдите размер Arraylist и извлеките элемент [требуемый элемент] в месте расположения индекса (size-2). Пожалуйста, помогите мне, если мой алгоритм имеет смысл

FYI
Другое, что я искал: Поместите два указателя и сохраните 1-й указатель на 1-й элемент и 2-й указатель на 3-м элементе и переместите их параллельно
Когда второй указатель достигает конца LinkList, извлеките узел [требуемый узел], на который указывает первый указатель

Лучший ответ:
  • Используйте два указателя: pointer-1 и pointer-2
  • make pointer-1 указывает на третий узел в одном связанном списке.

     pointer-1 = node1->next->next; // point to 3rd nd
    
     node1-->node2-->node3-->node4---> ...... -->node-last
                     ^
                     |
                    pointer-1
    
  • Теперь установите pointer-2 на первый узел

     pointer-2 = node1;   // point to 1st nd
    
     node1-->node2-->node3-->node4---> ...... -->node-last
       ^              ^
       |              |
      pointer-2      pointer-1
    
  • Теперь перейдите в связанный список в цикле, пока pointer-1 укажет на последний узел, в цикле также обновите указатель-2 (каждый раз до следующего узла)

    while (pointer-1->next!=NULL){// points to last node 
         pointer-1 = pointer-1 -> next;
         pointer-2 = pointer-2 -> next;
    }
    
    When loop ends pointer-1 points to last-node, pointer-2 points to third last
    
     node1-->node2-->........ ->node-l3-->node-l2-->node-last
                                 ^                   ^
                                 |                   |
                               pointer-2            pointer-1
    

Он работает в O (n) раз, где n — количество узлов в связанном списке.

Ответ №1

Поскольку связанный список связан по отдельности, вам нужно пройти его от начала до конца, чтобы узнать, что представляет собой элемент от третьего до последнего, os O(n) время неизбежно (если вы не указали указатель на третий-последний элемент в своем связанный список).

Ваша идея с двумя указателями будет использовать постоянное пространство. Вероятно, это лучший вариант, поскольку создание ArrayList будет иметь дополнительные накладные расходы и использовать больше места.

Ответ №2

Получите два указателя. pA, pB Переместить pA на 3 элемента вперед и pB на голову:

1->2->3->4-> .... ->99->100
|     |
pB    pA

После этого переместите оба указателя в один и тот же цикл, пока pA не достигнет последнего элемента.

В этот момент pB будет указывать на последний третий элемент

1->2->3->4-> .... ->98->99->100
|        |
pB       pA

Отредактировано: обход будет одним:

while(pA->next!=null){
pA = pA->next;
pB = pB->next;
}

Здесь pB будет третьим последним

Ответ №3

Альтернативный взгляд на решение этой проблемы, даже если это O (n)

Создайте пустой массив (n), запустите указатель на этот массив в 0 и начните с начала связанного списка. Каждый раз, когда вы посещаете узел, храните его в текущем индексе массива и продвигайте указатель массива. Продолжайте заполнять узлы в массиве, и когда вы достигнете конца массива, пожалуйста, начните с начала еще раз, чтобы перезаписать. Теперь, как только вы закончите окончательный конец списка, указатель nth elemtn из конца 🙂

Ответ №4

На практике Java LinkedList отслеживает свой размер, поэтому вы можете просто перейти к «list.get(list.size() -2)», но с построенным связанным списком я бы сделал следующее:

Храните массив из трех значений. По мере прохождения списка добавьте обновление в array[i%3]. Если значений больше нет, верните значение в array[(i-2)%3].

Ответ №5

Первое, что я хотел бы сделать, это попросить вас пересмотреть свое использование одного связанного списка. Почему бы просто не хранить ваши данные в ArrayList? Он делает все, что вам кажется нужным, и он встроен, поэтому он относительно эффективен по сравнению с тем, что большинство людей будет писать.

Если вы были связаны и решили использовать связанный список, я бы предложил сохранить прямой указатель на третий последний элемент (tle). Вставки просты — если они подошли к телевизору, ничего не делайте; если после этого, продвигайте указатель tle к следующему. Переезды — это скорее хлопот, но, вероятно, не в большинстве случаев. Если удаление происходит до tle, оно все еще остается. Досадная ситуация заключается в том, что элемент, подлежащий удалению, является tle или позже, и в этом случае вы должны пройти через итерацию с начала, пока следующая() ссылка текущего узла не будет tle. Текущий узел станет новым tle, и вы сможете продолжить удаление. Поскольку есть только три узла, которые ссылаются на этот уровень работы, вы, вероятно, будете делать все в порядке, если список значителен.

Окончательный вариант, если удаление из конца является частым явлением, заключается в том, чтобы сохранить список из списка назад. Затем tle становится третьим спереди для обслуживания.

Ответ №6
    //We take here two pointers pNode and qNode both initial points to head
//pNode traverse till end of list and the qNode will only traverse when difference
// between the count and position is grater than 0 and pthNode increments once
// in each loop
static ListNode nthNode(int pos){
ListNode pNode=head;
ListNode qNode=head;
int count =0;
while(qNode!=null){
count++;
if(count - pos > 0)
pNode=pNode.next;
qNode=qNode.next;
}
return pNode;
}

Оцените статью
TechArks.Ru
Добавить комментарий