учитывая узел, как я могу найти предыдущий узел в односвязном списке

Question

Учитывая текущий узел, как я могу найти его предыдущий узел в Единственном связанном списке. Благодарю. Логика подойдет, код ценится. Мы все знаем, что при наличии корневого узла можно выполнить последовательный обход, и я хочу знать, существует ли более разумный способ, позволяющий избежать издержек при последовательном доступе. (предположим, что нет доступа к корневому узлу) Спасибо.

Answer 1

Вы не можете.

Односвязные списки по определению связывают каждый узел только с его преемником, а не предшественником.Нет информации о предшественнике;даже не информация о том, существует ли он вообще (ваш узел может быть главой списка).

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

Вы можете сканировать всю кучу в поисках записи, которая выглядит как узел предшественника с указателем на ваш узел.(Не серьезное предложение.)

Answer 2

Ваш единственный вариант для односвязного списка - это линейный поиск, что-то вроде ниже (Python-подобный псевдокод):

find_previous_node(list, node):
   current_node = list.first
   while(current_node.next != null):
       if(current_node.next == node):
          return current_node
       else:
          current_node = current_node.next
   return null

Answer 3

Предполагая, что вы говорите о прямом односвязном списке (каждый узел имеет только указатель на «следующий» и т. Д.), Вам придется выполнять итерацию с начала списка, пока вы не найдете узел, у которого «следующий» равенна ваш текущий узел.Очевидно, что это медленная O(n) операция.

Надеюсь, это поможет.

Answer 4

Пройдите по списку с самого начала, пока не встретите узел, чья ссылка next указывает на ваш текущий узел.

Но если вам нужно это сделать, возможно, вам не следует использовать односвязныесписок на первом месте.

Answer 5

Мы можем перемещаться по LinkedList, используя медленные и быстрые указатели.Допустим,

быстрый указатель fast = fast.next.next

медленный указатель slow = slow.next

Медленный указатель всегда будет предшествоватьбыстрый указатель, и мы можем его найти.

Answer 6

Сохранить двух указатель (curr, prev) изначально оба будут указывать на заголовок списка.

выполняйте цикл в списке, пока не достигнете конца списка или нужного узла.

для каждой итерации перемещайте узел curr к следующему, но перед переходом к следующему сохраните его указатель в указателе prev.

    prev = curr; // first store current node in prev
    curr = curr->next // move current to next

в конце цикла prev узел будет содержать предыдущий узел.

getPrev(head, key) {    
    Node* curr = head;
    Node* prev = head;
    while(curr !=null && curr->data==key){
        prev = curr;
        curr = curr->next
    }
    return prev
}

Пример:

список = 1-> 5-> 10-> 4-> 3

Мы хотим, чтобы предыдущий узел равнялся 4. Итак, ключ = 4 и начальная точка на 1

первоначально:

• температура будет указывать на 1
• prev будет указывать на 1

итерация 1:

• Сначала присвойте prev = temp (предыдущая точка 1)
• темп перемещения; temp-> next (временная точка до 5)

итерация 2:

• Сначала присвойте prev = temp (предыдущая точка 5)
• темп перемещения; temp-> next (временная точка до 10)

итерация 3:

• Сначала присвойте prev = temp (предыдущая точка 10)
• темп перемещения; temp-> next (временная точка до 4)

итерация 4:

• temp-> data == ключ, поэтому он вернется из цикла.
• вернуть предыдущий узел

Answer 7

Вот небольшой трюк с линейным поиском: просто перейдите к узлу или его позиции, чей предыдущий узел вы ищете:

private MyNode findNode(int pos) {
//node will have pos=pos-1
        pos-- = 1; 
        MyNode prevNode = null;
        int count = 0;  
        MyNode p = first.next;  // first = head node, find it however you want.
//this is for circular linked list, you can use first!=last for singly linked list
        while (p != first) { 
            if (count == pos) {
                prevNode = p;
                break;
            }
            p = p.next;
            count++;
        }
        return prevNode;
    }

Answer 8

Это какой-то хак, который я обнаружил при решении проблемы (Удалить каждый четный узел в списке)

    internal void DeleteNode(int p)
    {
        DeleteNode(head, p);
    }

    private void DeleteNode(Node head, int p)
    {
        Node current = head;
        Node prev = null;

        while (current.next != null)
        {
            prev = current;
            current = current.next;
            if (current.data == p)
            {
                prev.next = current.next;
            }
        }
    }

Теперь здесь, в prev, вы назначаете ток, а затем перемещаете ток в следующий, таким образом, prev содержит предыдущий узел. Надеюсь, это поможет ...

Answer 9

Используйте метод nodeAt () и передайте заголовок, размер и индекс текущего узла.

 public static Node nodeAt(Node head,int index){
    Node n=head;
    for(int i=0;i<index;i++,n=n.next)
      ;
    return n;
  }

, где n возвращает узел предшественника.

Answer 10

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

while(node)
{
      previous = node
      node = node.next
      // Do what ever you want to do with the nodes
}