Как найти n-й элемент с конца одного связанного списка?

Ответ 1

Ваш алгоритм работает, сначала создавая ссылки на два узла в связанном списке, которые разделены N узлами. Таким образом, в вашем примере, если N равно 7, тогда он установит p1-8 и p2 в 4.

Затем он будет перемещать каждую ссылку node на следующий node в списке, пока p2 не достигнет последнего элемента в списке. Опять же, в вашем примере это будет, когда p1 равно 5 и p2 равно 10. В этот момент p1 ссылается на Nth на последний элемент в списке (по свойству, что они являются N узлами друг от друга).

Ответ 2

Ключ к этому алгоритму состоит в том, чтобы сначала установить два указателя p1 и p2 на узлы n-1, поэтому мы хотим, чтобы p2 указывал на (n-1)th node с начала списка, тогда мы перемещаем p2 до достижения last node списка. Как только p2 достигнет конца списка, p1 будет указывать на nth node с конца списка.

Я добавил объяснение в виде комментариев. Надеюсь, это поможет:

// Function to return the nth node from the end of a linked list.
// Takes the head pointer to the list and n as input
// Returns the nth node from the end if one exists else returns NULL.
LinkedListNode nthToLast(LinkedListNode head, int n) {
  // If list does not exist or if there are no elements in the list,return NULL
  if (head == null || n < 1) {
    return null;
  }

  // make pointers p1 and p2 point to the start of the list.
  LinkedListNode p1 = head;
  LinkedListNode p2 = head;

  // The key to this algorithm is to set p1 and p2 apart by n-1 nodes initially
  // so we want p2 to point to the (n-1)th node from the start of the list
  // then we move p2 till it reaches the last node of the list. 
  // Once p2 reaches end of the list p1 will be pointing to the nth node 
  // from the end of the list.

  // loop to move p2.
  for (int j = 0; j < n - 1; ++j) { 
   // while moving p2 check if it becomes NULL, that is if it reaches the end
   // of the list. That would mean the list has less than n nodes, so its not 
   // possible to find nth from last, so return NULL.
   if (p2 == null) {
       return null; 
   }
   // move p2 forward.
   p2 = p2.next;
  }

  // at this point p2 is (n-1) nodes ahead of p1. Now keep moving both forward
  // till p2 reaches the last node in the list.
  while (p2.next != null) {
    p1 = p1.next;
    p2 = p2.next;
  }

   // at this point p2 has reached the last node in the list and p1 will be
   // pointing to the nth node from the last..so return it.
   return p1;
 }

В качестве альтернативы мы можем установить p1 и p2 отдельно n узлами вместо (n-1), а затем переместить p2 до конца списка, а не перемещаться до последнего node:

LinkedListNode p1 = head;
LinkedListNode p2 = head;
for (int j = 0; j < n ; ++j) { // make then n nodes apart.
    if (p2 == null) {
        return null;
    }
    p2 = p2.next;
}
while (p2 != null) { // move till p2 goes past the end of the list.
    p1 = p1.next;
    p2 = p2.next;
}
return p1;

Ответ 3

Что вы думаете об этом подходе.

• Рассчитать длину связанного списка.
• Фактический Node индекс с головы = длина связанного списка - данный индекс;
• Напишите функцию travesre из головы и получите Node по указанному выше индексу.

Ответ 4

//this  is the recursive solution


//initial call
find(HEAD,k);

// main function
void find(struct link *temp,int k)
{  
 if( temp->next != NULL)
   find( temp->next, k);
 if((c++) == k)       // c is initially declared as 1 and k is the node to find from last.
  cout<<temp->num<<' ';
}

Ответ 5

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

Вы можете сделать это, пропуская список только один раз (плюс немного), используя постоянное дополнительное пространство:

Node *getNthFromEnd(Node *list, int n) {

    if (list == null || n<1) {
        return null; //no such element
    }

    Node *mark1 = list, *mark2 = list, *markend = list;
    int pos1 = 0, pos2 = 0, posend = 0;

    while (markend!=null) {
        if ((posend-pos2)>=(n-1)) {
            mark1=mark2;
            pos1=pos2;
            mark2=markend;
            pos2=posend;
        }
        markend=markend->next;
        ++posend;
    }
    if (posend<n) {
        return null; //not enough elements in the list
    }

    //mark1 and mark2 are n-1 elements apart, and the end is at least
    //1 element after mark2, so mark1 is at least n elements from the end

    while((posend - pos1) > n) {
      mark1 = mark1->next;
      ++pos1;
    }
    return mark1;
}

Эта версия использует 2 дополнительных указателя, менее чем N+n traversals, где N - длина списка, а N - аргумент.

Если вы используете дополнительные указатели M, вы можете получить это до N+ceil(n/(M-1)) (и вы должны сохранить их в круговом буфере)

Ответ 6

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

Я предлагаю вам запустить этот код на небольшом наборе данных образца. Используйте ваш отладчик для поочередного запуска строк (вы можете установить точку останова в начале функции). Это должно дать вам представление о том, как работает код.

Вы также можете Console.WriteLine() вывести интересующие переменные.

Ответ 7

Еще одно решение этой проблемы. Хотя временная сложность остается прежней, этот код достигает решения в одном цикле.

public Link findKthElementFromEnd(MyLinkedList linkedList, int k)
    {
        Link current = linkedList.getFirst();//current node
        Link currentK = linkedList.getFirst();//node at index k

        int counter = 0;

        while(current.getNext()!=null)
        {
            counter++;

            if(counter>=k)
            {
                currentK = currentK.getNext();
            }

            current = current.getNext();
        }

        //reached end
        return currentK;
    }

Ответ 8

Просто отмените связанный список в линейном времени и найдите k-й элемент. Он по-прежнему работает в линейном режиме.

Ответ 9

Вы можете просто перебрать связанный список и получить размер. Как только у вас есть размер, вы можете найти n-й член в 2n, который еще есть O (n).

public T nthToLast(int n) {
    // return null if linkedlist is empty
    if (head == null) return null;

    // declare placeholder where size of linkedlist will be stored
    // we are hoping that size of linkedlist is less than MAX of INT
    int size = 0;

    // This is O(n) for sure
    Node i = head;
    while (i.next != null) {
        size += 1;
        i = i.next;
    }

    // if user chose something outside the size of the linkedlist return null
    if (size < n)
        return null;

    // This is O(n) if n == size
    i = head;
    while(size > n) {
        size--;
        i = i.next;
    }

    // Time complexity = n + n = 2n
    // therefore O(n)

    return i.value;
}

Ответ 10

Решение в С#. Создайте LinkedList с фиктивными значениями.

  LinkedList<int> ll = new LinkedList<int>();
            ll.AddFirst(10);
            ll.AddLast(12);
            ll.AddLast(2);
            ll.AddLast(8);
            ll.AddLast(9);
            ll.AddLast(22);
            ll.AddLast(17);
            ll.AddLast(19);
            ll.AddLast(20);

Создайте 2 указателя p1 & p1, которые указывают на первый узел.

        private static bool ReturnKthElement(LinkedList<int> ll, int k)
        {
            LinkedListNode<int> p1 = ll.First;
            LinkedListNode<int> p2 = ll.First;

Итерация по циклу до тех пор, пока p2 не станет нулевым - это означает, что длина связного списка меньше K-го элемента ИЛИ до K-го элемента

            for (int i = 0; i < k; i++)
            {
                p2 = p2.Next;
                if (p2 == null)
                {
                    Console.WriteLine($"Linkedlist is smaller than {k}th Element");
                    return false;
                }
            }

Теперь итерируйте оба указателя, пока p2 не станет нулевым. Значение, содержащееся в указателе p1, будет соответствовать K-му элементу

            while (p2 != null)
            {
                p1 = p1.Next;
                p2 = p2.Next;
            }
            //p1 is the Kth Element
            Console.WriteLine($"Kth element is {p1.Value}");
            return true;
        }

Ответ 11

У меня есть рекурсивное решение в другом потоке в StackOverflow здесь

Ответ 12

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

Ответ 13

Возьмем здесь два указателя pNode и qNode, обе начальные точки на голову qNode. Затем переходите до конца списка, и pNode будет проходить только тогда, когда разница между количеством отсчетов и позицией больше 0 и pthNode увеличивается один раз в каждом цикле.

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

Ответ 14

public int nthFromLast(int n){
    Node current = head;
    Node reference = head;      
    for(int i=0;i<n;i++){
        reference=reference.getNext();
    }
    while(reference != null){
        current = current.getNext();
        reference = reference.getNext();
    }
    return current.getData();
}

Ответ 15

Используйте два указателя pTemp и NthNode. Изначально обе точки указывают на node списка. NthNode начинает движение только после того, как pTemp выполнил n ходов. От обоих движений вперед, пока pTemp не достигнет конца списка. В результате NthNode указывает на nth node с конца связанного списка.

public ListNode NthNodeFromEnd(int n){
    ListNode pTemp = head, NthNode = null;
   for(int count=1; count<n;count++){
     if(pTemp!=null){
       pTemp = pTemp.getNext();
     }
   }
   while(pTemp!=null){
     if(NthNode==null){
         NthNode = head;
     }
     else{
        NthNode = NthNode.getNext();
     }
     pTemp = pTemp.getNext();
   }
   if(NthNode!=null){
     NthNode = NthNode.getNext();
     return NthNode;
   }
return null;
}

Refer TextBook: "Структура данных и алгоритмы упрощены на Java"

Ответ 16

Чтобы понять эту проблему, мы должны сделать простую аналогию с примером измерения. Скажите, вы должны найти место своей руки, где ровно 1 метр от вашего среднего пальца, как бы вы измерили? Вы просто возьмете линейку длиной в 1 метр и поставьте верхнюю часть этой линейки на кончик вашего среднего пальца, а нижний конец метра будет ровно в 1 метре от вершины вашего среднего пальца, палец.

То, что мы делаем в этом примере, будет таким же, нам просто нужен кадр с n-элементом в ширину, и нам нужно положить кадр в конец списка, таким образом, начало node кадра будет ровно n-м элементом в конце списка.

Это наш список, предполагающий, что у нас есть M элементов в списке, а наш кадр с N-элементом широкий;

HEAD -> EL(1) -> EL(2) -> ... -> EL(M-1) -> EL(M)

<-- Frame -->

Однако нам нужны только границы рамки, поэтому конечная граница кадра будет точно (N-1) элементов от начальной границы кадра. Поэтому нужно хранить только эти граничные элементы. Пусть назовем их A и B;

HEAD -> EL(1) -> EL(2) -> ... -> EL(M-1) -> EL(M)

A <- N-Element Wide-> B

Первое, что нам нужно сделать, это найти B, который является концом фрейма.

ListNode<T> b = head;
int count = 1;

while(count < n && b != null) {
    b = b.next;
    count++;
}

Теперь b является n-м элементом массива, а a находится на HEAD. Таким образом, наш кадр установлен, что мы будем делать, это постепенно увеличивать оба граничных узла до тех пор, пока b не дойдет до конца списка, где a будет n-й последний элемент;

ListNode<T> a = head;

while(b.next != null) {
    a = a.next;
    b = b.next;
}

return a;

Чтобы собрать все и с проверками HEAD, N < M (где M - размер списка) и другие вещи, вот полный метод решения;

public ListNode<T> findNthToLast(int n) {
    if(head == null) {
        return null;
    } else {
        ListNode<T> b = head;
        int count = 1;

        while(count < n && b != null) {
            b = b.next;
            count++;
        }

        if(count == n && b!=null) {
            ListNode<T> a = head;

            while(b.next != null) {
                a = a.next;
                b = b.next;
            }

            return a;
        } else {
            System.out.print("N(" + n + ") must be equal or smaller then the size of the list");
            return null;
        }
    }
}

Ответ 17

Я думаю, что есть один недостаток в вопросительном коде, и мне интересно, было ли это взято из книги, как это возможно... он может выполняться правильно, но код несколько логически неверен. Внутри цикла for... условие if должно быть проверено на p2->next ! = NULL

 for (int j = 0; j < n - 1; ++j) { // skip n-1 steps ahead
       if (p2->next == null) {
       return null; // not found since list size < n
   }

... остальное хорошо и объяснение, как уже сказано, сдвиг кода p2 (n-1) продвигается вперед до p1, затем в цикле while он перемещает их одновременно, пока p2->next не достигнет конца. скажите, если вы нашли неправильный ответ

Ответ 18

Вы также можете решить указанную выше проблему с помощью хеш-таблиц. Записи хэш-таблицы - это позиция node и адрес node. Поэтому, если мы хотим найти nth node с конца (это означает, что m-n + 1 из первого, где m - количество узлов). Теперь, когда мы вводим записи хеш-таблицы, мы получаем количество узлов. Шаги: -

1. Переверните каждый node и сделайте соответствующие записи в хеш-таблице.

2. Посмотрите на m-n + 1 node в хэш-таблице, мы получим адрес.

Сложность времени - O (n).

Ответ 19

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

Вот мой код:

    public void findntolast(int index)
    {
        Node ptr = front; int count = 0;
        while(ptr!=null)
        {
            count++;
            if (count == index)
            {
                front = ptr;
                break;
            }
            ptr = ptr.next;
        }
        Node temp=front;
        while(temp!=null)
        {
            Console.WriteLine(temp.data);
            temp=temp.next;
        }
    }

Ответ 20

Рекурсивное решение:

Node findKth (Node head, int count, int k) {
    if(head == null)
        return head;
    else {
        Node n =findKth(head.next,count,k);
        count++;

        if(count == k)
            return head;

        return n;
    }
}

Ответ 21

можете ли вы использовать дополнительную структуру данных.. если так будет просто... начните толкать все узлы в стек, поддерживайте счетчик поп файлом. в соответствии с вашим примером, 8- > 10- > 5- > 7- > 2- > 1- > 5- > 4- > 10- > 10 начните чтение связанного списка и начните толкать узлы или node → данных в стек. поэтому стек будет выглядеть как top → {10, 10,4, 5, 1, 2, 7, 5, 10, 8} < -bottom.

теперь начинает выскакивать из верхней части стека, поддерживая счетчик = 1, и каждый раз, когда вы пополняете счетчик на 1, когда вы достигаете n-го элемента (в вашем примере 7-го элемента), перестаете появляться.

Примечание: это приведет к печати или извлечению данных/узлов в обратном порядке.

Ответ 22

Вот код с использованием двух указателей: (источник)

Медленный и быстрый поиск указателей

struct node
{
  int data;
  struct node *next;
}mynode;


mynode * nthNodeFrmEnd(mynode *head, int n /*pass 0 for last node*/)
{
  mynode *ptr1,*ptr2;
  int count;

  if(!head)
  {
    return(NULL);
  }

  ptr1  = head;
  ptr2  = head;
  count = 0;

  while(count < n)
  {
     count++;
     if((ptr1=ptr1->next)==NULL)
     {
        //Length of the linked list less than n. Error.
        return(NULL);
     }
  }

  while((ptr1=ptr1->next)!=NULL)
  {
    ptr2=ptr2->next;
  }

  return(ptr2);
}

рекурсии

node* findNthNode (node* head, int find, int& found){
    if(!head) {
        found = 1;
        return 0;
    }
    node* retval = findNthNode(head->next, find, found);
    if(found==find)
        retval = head;
    found = found + 1;
    return retval;
}

Ответ 23

мой подход, что я считаю простым и имеет временную сложность O (n).

Шаг 1: сначала получите количество узлов. Запустите цикл for, начиная с первого node до последнего node

Шаг 2. После того, как у вас есть счетчик, примените простую математику, например, если мы найдем 7-й node до последнего node, а число всех узлов равно 12, тогда (count-index) - 1 будет введите kth node, до которого вам нужно будет пройти, и это будет nth node до последнего node. В этом случае (12 -7) -1 = 4

Если элементы 8- > 10- > 5- > 7- > 2- > 1- > 5- > 4- > 10- > 10, то результат равен 7-му последнему node равен 7, что ничего, кроме 4-го node с самого начала.

Ответ 24

В java я буду использовать

public class LL {
  Node head;
  int linksCount;

   LL(){
     head = new Node();
     linksCount = 0;
   }

  //TRAVERSE TO INDEX
  public Node getNodeAt(int index){
    Node temp= head;
    if(index > linksCount){
        System.out.println("index out of bound !");
        return null;
    }
    for(int i=0;i<index && (temp.getNext() != null);i++){
        temp = temp.getNext();
    }
    return temp.getNext();
  }
}

Ответ 25

Никто здесь не заметил, что версия Джонатана выкинет исключение NullPinterException, если n больше длины LinkedList. Вот моя версия:

public Node nth(int n){
        if(head == null || n < 1) return null;

        Node n1 = head;
        Node n2 = head;
        for(int i = 1; i < n; i++){
            if(n1.next == null) return null; 
            n1 = n1.next;
        }

        while (n1.next != null){
            n1 = n1.next;
            n2 = n2.next;
        }
        return n2;
}

Я просто немного изменяю здесь: когда node n1 шаг вперед, вместо того, чтобы проверять, является ли n1 нулевым, я проверяю, что погода n1.next равно null, или же в while цикл n1.next будет генерировать исключение NullPinterException.

Ответ 26

Вот версия С# для поиска n-го дочернего элемента из списка ссылок.

public Node GetNthLast(Node head, int n)
    {
        Node current, nth;
        current = nth = head;
        int counter = 0;

        while (current.next != null)
        {
            counter++;
            if (counter % n == 0)
            {
                for (var i = 0; i < n - 1; i++)
                {
                    nth = nth.next;
                }
            }
            current = current.next;
        }
        var remainingCounts = counter % n;
        for (var i = 0; i < remainingCounts; i++)
        {
            nth = nth.next;
        }
        return nth;
    }

Ответ 27

В зависимости от допустимой стоимости памяти (O (k) в этом решении) мы могли бы выделить массив указателей длины k и заполнить его узлами в виде кругового массива при обходе связанного списка.

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

Если первый элемент массива равен NULL, решение нашей проблемы отсутствует.

Ответ 28

Прежде всего

Как упомянуто в комментарии, но, чтобы быть более ясным, вопрос от:

<Cracking the coding interview 6th> | IX Interview Questions | 2. Linked Lists | Question 2.2.

Это отличная книга от Gayle Laakmann McDowell, инженера-программиста из Google, которая опросила множество людей.

подходы

(Предполагая, что связанный список не отслеживает длину), есть 2 подхода за время O (n) и пространство O (1):

• Сначала найдите длину, затем зацикливайтесь на элементе (len-k + 1).
  Это решение не упоминается в книге, насколько я помню.
• Цикл, через 2 указателя, держите их (k-1) на расстоянии.
  Это решение из книги, как и в вопросе.

Код

Ниже приведена реализация в Java с модульным тестом (без использования какой-либо продвинутой структуры данных в самом JDK).

KthToEnd.java

/**
 * Find k-th element to end of singly linked list, whose size unknown,
 * <p>1-th is the last, 2-th is the one before last,
 *
 * @author eric
 * @date 1/21/19 4:41 PM
 */
public class KthToEnd {
    /**
     * Find the k-th to end element, by find length first.
     *
     * @param head
     * @param k
     * @return
     */
    public static Integer kthToEndViaLen(LinkedListNode<Integer> head, int k) {
        int len = head.getCount(); // find length,

        if (len < k) return null; // not enough element,

        return (Integer) head.getKth(len - k).value; // get target element with its position calculated,
    }

    /**
     * Find the k-th to end element, via 2 pinter that has (k-1) distance.
     *
     * @param head
     * @param k
     * @return
     */
    public static Integer kthToEndVia2Pointer(LinkedListNode<Integer> head, int k) {
        LinkedListNode<Integer> p0 = head; // begin at 0-th element,
        LinkedListNode<Integer> p1 = head.getKth(k - 1); // begin at (k-1)-th element,

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

        return p0.value;
    }

    static class LinkedListNode<T> {
        private T value;
        private LinkedListNode next;

        public LinkedListNode(T value) {
            this.value = value;
        }

        /**
         * Append a new node to end.
         *
         * @param value
         * @return new node
         */
        public LinkedListNode append(T value) {
            LinkedListNode end = getEnd();
            end.next = new LinkedListNode(value);
            return end.next;
        }

        /**
         * Append a range of number, range [start, end).
         *
         * @param start included,
         * @param end   excluded,
         */
        public void appendRangeNum(Integer start, Integer end) {
            KthToEnd.LinkedListNode last = getEnd();
            for (int i = start; i < end; i++) {
                last = last.append(i);
            }
        }

        /**
         * Get end element of the linked list this node belongs to, time complexity: O(n).
         *
         * @return
         */
        public LinkedListNode getEnd() {
            LinkedListNode end = this;
            while (end != null && end.next != null) {
                end = end.next;
            }

            return end;
        }

        /**
         * Count of element, with this as head of linked list.
         *
         * @return
         */
        public int getCount() {
            LinkedListNode end = this;
            int count = 0;
            while (end != null) {
                count++;
                end = end.next;
            }

            return count;
        }

        /**
         * Get k-th element from beginning, k start from 0.
         *
         * @param k
         * @return
         */
        public LinkedListNode getKth(int k) {
            LinkedListNode<T> target = this;
            while (k-- > 0) {
                target = target.next;
            }

            return target;
        }
    }
}

KthToEndTest.java

(unit тест, используя TestNG, или вы изменяете на JUnit/.., как хотите)

import org.testng.Assert;
import org.testng.annotations.BeforeClass;
import org.testng.annotations.Test;

/**
 * KthToEnd test.
 *
 * @author eric
 * @date 1/21/19 5:20 PM
 */
public class KthToEndTest {
    private int len = 10;
    private KthToEnd.LinkedListNode<Integer> head;

    @BeforeClass
    public void prepare() {
        // prepare linked list with value [0, len-1],
        head = new KthToEnd.LinkedListNode(0);
        head.appendRangeNum(1, len);
    }

    @Test
    public void testKthToEndViaLen() {
        // validate
        for (int i = 1; i <= len; i++) {
            Assert.assertEquals(KthToEnd.kthToEndViaLen(head, i).intValue(), len - i);
        }
    }

    @Test
    public void testKthToEndVia2Pointer() {
        // validate
        for (int i = 1; i <= len; i++) {
            Assert.assertEquals(KthToEnd.kthToEndVia2Pointer(head, i).intValue(), len - i);
        }
    }
}

Подсказки:

• KthToEnd.LinkedListNode
  Это простой односвязный узел списка, реализованный с нуля, он представляет собой связанный список, начинающийся с самого себя.
  Кроме того, он не отслеживает голову/хвост/длину, хотя у него есть методы для этого.